Hmmm... I'm thinking that yeah, start fighter and then go off to pick up ranger levels. Horse animal companion, archery track, and yes, definately get the pixie cohort.

Paladin ALMOST gets what you need (Come on, ability to summon mount out of thin air? TOO perfect. Immunity to Fear effects? Friggin' perfect. Blessed by Gods? Yet again, spot on.) However, the healing/turn undead has got to go. Maybe some variant paladin, like the hunter-Paladin (Give up healing for Favored Enemies) or something like that would be good for 5 levels. Granted, then you've got a spare animal companion or something, so I'm not sure on the whole paladin thing.