See if you can stack a Cavalier's Mount with Paladin's once you reach Paladin 5 for determining your effective druid level. If so, consider starting as a Cavalier 2, if not you may still want (Emissary) Cavalier 1 just to help with starting feats.
Using gnome, your 20 point buy stats should be Str 12 Dex 14 Con 16 Int 12 Wis 7 Cha 18.
As an Emissary, you can start with a wolf mount (with free light armor proficiency) and Mounted Combat as a bonus feat (and the ability to move full speed in medium armor). So you'll also have Ride-by Attack, and can have Spirited Charge by 3rd level. Going to Cav 2 nets you an Order ability, but I'd only go to 2 if you can stack the levels for Paladin mount. Otherwise, pick order based on the class skills and which has the least pain in the ass edicts, though by RAW the worst that happens for violating them is loss of your 1/day crappy chalenge ability. DM might not like you breaking your edicts every day, though.
Some good orders:
[spoiler]Ronin ("Knight Errant"): Gives Know (local) and Suvival as class skills. You get to make your own edicts, so just copy/paste the Paladin code you're stuck with anyway. Has the BEST level 2 ability: basically Slippery Mind + reroll on stabilization checks.
Dragon: Perception and suvival are excellent class skills, especially Perception. Edicts are super-easy for a Paladin to keep up. Level ability sucks hard, though, don't go to Cav 2 for it.
Cockatrice: Appraise and Perform aren't great, but at least they're not Paladin skills. Putting yourself first may clash alot with Paladin. Level 2 ability is solid awesome for Intimidation builds, which Paladin can be great at, but you'll lack the feats to do well.
Star: Neither class skill adds anything new. But the edict is "be a paladin," and the level 2 ability gives you some stuff to do during a prep round should there be any, before a combat, and makes you fall one less level behind on lay on hands instead of 2.
Lion: The class skills suck for you, and the edicts require you to be some NPC's underling, bleh. Only reason this is good is if the level 2 ability is unlimited use, and even then probably not.
[/spoiler]
Alternatively, Dragoon Fighter 1 trades the bonus feat for Mounted Combat and Skill Focus (Ride). Basically, I just think you really, REALLY want that Spirited Charge by level 3 rather than level 5.