Well I finally sat down and did a formal analysis of the three main choices. Celestial Heavy Warhorse (CHWH), Dire Wolf and a Griffon.
The advancement is
Code:
Pal Lv CHWH DW Pal Lv Griffon
lv 6 6HD+18 8HD+24 N/A
lv 9 8HD+24 10HD+30 lv 8 9HD+27
lv 12 10HD+30 12HD+36 lv 11 11HD+55*
lv 16 12HD+36 14HD+42 lv 14 13HD+65
+ 12HD+36 14HD+42 lv 18 15HD+75
* Griffon advances to Huge at 11 HD gaining +8 Str, +4 Con
The Dire Lion is not worth it as it effectively is the same as the Dire Wolf only with a different set of special attacks.
Since the other stats are advanced at the same rate, there's no advantage to charting them. The horse is the weakest of the 3 at 18 str, the dire wolf has a 25 and the griffon starts out at 18, but gets bumped up to 26 at 11HD.
The griffon also has the best AC of the three. CHWH and DW are 14. the Griffon has a base 17 rising to 19 at 11HD. Gaining a total of +2 Natural armor from the Size increase. However the Griffon's ability to wear armor is compromised by it's limitation to a light load. though at a light load of 918 lb. (after Size increase), it might not be that bad especially considering that it already has 5 points of ac on the others.
The CHWH is clearly the worst of the three it's only advanages being the elemental resistances and DR gained through the template (Smite is more than cancelled out by the Str differential). Furthermore, since most elemental attacks are area effect spells of one sort or another, that advantage is minimized due to the improved evasion feat gained by all mounts (1/2 dam or none). A collar of resistance (MotW) is only 12,250 gold for a +5 to all saves. Between that and the save bonuses and spell sharing, the mount should be pretty much immune to area effect attacks.
The DR is gained at sufficient levels that it probably will not be effective vs the creatures that will be encountered.
If you want something early on, the dire wolf, is clearly the best choice. It's nearly as tough as the griffon and is superior up until the griffon hits the size increase to huge. It's automatic trip attack should not be underestimated as well.
If you can keep the griffon alive (shouldn't be that difficult) until it hits 11HD, it becomes hands down the best of the three.
One possible suggestion that could be very interesting would be a Bulette possibly with either a half celestial or Axiomatic template (MotP). They are extremely tough with high HP (94), Ac 22 and great attacks. While one would defintely not be a standard, mount (due to their relentless hunger and agression). The half-celestial or axiomatic (lawful) template should provice sufficent justification for overcoming that (not to mention making it even tougher). The one drawback is that it would probably not be takeable until probably 11th (CR7) or plus what ever the template adds. In any case the burrowing abilty adds a whole host of interesting posibilities and should keep it out of danger in most situations should that be necessary.