A lot of good ideas in here, I really appreciate it!
One thing I do want to keep in mind is that the mount somewhat scales with level. Statting out a celestial warhorse for a 6th level paladin, my first reaction was to double-take, as it's a formidable combatant for 12 hours a day. And while I don't want to go over the top, I would like to replace the mount with something reasonably equivalent.
Consider:
[SBLOCK]Warhorse, celestial heavy: magical beast (extraplanar); Size L; HD 6d8+24; hp 51; Init +1; Spd 50 ft.; AC 18 (-1 size, +1 Dex, +8 natural), touch 10, flat-footed 13; BAB/Grp +4/+12; Attack: Hoof +7 melee (1d6+4/x2); Full Attack: 2 hooves +7 melee (1d6+4/x2) and bite +2 melee (1d4+2/x2); SA Smite evil 1/day; SQ DR 5/magic, Darkvision 60 ft., empathic link, energy resistances (acid 5, cold 5, electricity 5), improved evasion, low-light vision, scent, share spells, share saving throws, SR 11; AL NG; SV Fort +8, Ref +6, Will +3; Str 19 (+4), Dex 13 (+1), Con 17 (+3), Int 6 (-2), Wis 13 (+1), Cha 6 (-2).
Skills: Listen +6, Spot +5. Feat: Endurance, Improved toughness, Run.
Smite Evil (Su): Once per day a celestial creature can make a normal melee attack to deal extra damage equal to its HD (maximum of +20) against an evil foe.
Carrying Capacity: A light load for a heavy warhorse is up to 300 pounds; a medium load, 301–600 pounds; and a heavy load, 601–900 pounds. A heavy warhorse can drag 4,500 pounds.[/SBLOCK]
That said, I do like a lot of the suggestions already mentioned, in particular the Paladin's Boon and the option to take Weapon Specialization for one time only.
Cheers,
Vurt