A friend of mine is making a Paladin archer for a campaign he's in, and is wondering if there is an animal limit to what he can choose.
Heavy horse for medium, pony for small. Camels, boars, and dogs are also allowed by the class. All there in the CRB divine bond ability.
I know, not exciting, but you have full druid level (saving yourself a feat) and the companion has int 6 (so it can take any feat it qualifies for from the get go, as well as a language to ease up instructions)
Also, it can be left in a friendly pocket dimension when not in use- you just call it when you need it (no stated time limit though- just store it as you want). Plus, it get the celestial template (DR, some resistances, smite) and fairly good spell resistance.
Of course, there is the general penalty for letting it die (30 days to get a new one, -1 on attack/damage), but eh.
Anyway, you want better options, you need to find your own methods. Half orcs, for instance, can take the beast rider feat at level 7 to get some nice big options: some dinosaurs, a pterosaur, elephants, and rhinos.