As others have suggested, combining the Leadership cohort and Special Mount is your best bet. If you don't want to take 5 levels of Paladin to get a Special Mount, Harmonium Peacekeeper from Dragon 315 gets at 1st level, as per a 5th level Paladin (What's more, levels of Paladin stack with Harmonium Peacekeeper, ie, a Fighter 5/Paladin 3/Harmonium Peacekeeper 1 has the special mount of a 8th level Paladin - REALLY useful for Supermount builds).
ie, a Fighter 5/Paladin 3/Harmonium Peacekeeper 1
Fighter 5
Fighter 5
5 levels of fighter
...explain this one.
Every build needs 5 levels of fighter.
Every build. I know Fighter 4 is a more traditional breakoff point, but that's only because people seem to think that not gaining any special abilities, feats, increases to saves, or anything at all besides 1 point of BAB somehow makes Fighter 5 undesirable. Crazy buggers.
More seriously, I got nothing. I was going by memory in trying to just put down the Dragon Magazine leadin to the class, but a review of Dragon 315 shows that even it's got Fighter 6/Paladin 3/Harmonium Peacekeeper 1 as its example build.
Anklebite, if it makes you feel any better, how about Crusader 5/Paladin 1/Harmonium Peacekeeper 1, for illustrating the point that Paladin and Harmonium Peacekeeper levels stack?