Worship Mara, max diplomacy/ride, barrel around on your mount talking your way out of everything. Kill what you can't quell. Paladins aren't terribly complicated, really, just make sure you turn off complicity. Kobolds (giant dragonfly, no joke.) and halflings (hippogriff, selection of dragons, excellent stats for a paladin) make excellent paladins, because they get some killer sacred mounts.
Here's the spoiler info on sacred mounts and animal companions:
This took waaay too much time in wizardmode. Anyway, an addendum to
the stats -- which sacred mounts the various races get. There's some
oddities with sizing -- all the dragons, no matter the size category,
seem to be ridable. Some non-dragons -- I noticed the elephants, but I
may have missed a few -- will require resizing of you or them to be
ridden. Anything marked (OS) is unridable with that race's default
size category, everything marked (UR) is unridable, period. Anything
''ed is a case where the display name isn't what the critter is, such
as with unicorns -- this may only happen in the case of characters
with low knowledge scores. The actual creature is in parenthesis
beside them, as is the type of dragon for those particular mounts.
Notes, if any, are beside the race name.
Some pretty impressive stuff, those paladins get to ride around on.
How come blackgaurds don't get such neat toys, eh?
Human
celestial horse, celestial warhorse, dragonne, griffin,
'horse' (Unicorn), juvenile dragon(Gold), lammasu, pegasus, young
dragon(Gold)
Dwarf: All mounts celestial.
arsinoitherium, black bear(UR), elephant(OS), giant tortoise,
grick(UR), pony, rust monster(UR), warpony, dire elephant(OS)
Halfling
celestial aurumvorax, celestial cheetah celestial mastiff, celestial
pony, celestial rust monster(UR), celestial warpony, celestial wolf,
hippogriff, juvenile dragon (Brass), juvenile dragon(Bronze), young
dragon(Brass), young dragon(Bronze)
Kobold: All mounts celestial.
cave cricket, giant blue beetle(UR), giant crustacean(UR), giant
dragonfly, giant praying mantis, giant slug, giant soldier ant, giant
wasp, grick(UR), monsterous centipede(UR)
Elf
celestial horse, celestial pegasus, celestial warhorse, hippogriff,
'horse' (Unicorn), juvenile dragon(Silver), young dragon(Silver)
Lizardfolk: All dragon mounts are actually ur-dragons.
behir(UR), celestial riding lizard, celestial war lizard,
froghemoth(UR), tendriculous(UR), young dragon(Water), young
dragon(Plant), young dragon(Shadow), young dragon(Shattering), young
dragon(Brilliant)
Gnome
celestial aurumvorax, celestial giant badger(UR), celestial hatori,
celestial mastiff, celestial pygmy war rhino, celestial riding dog,
juvenile dragon(Brass), juvenile dragon(Copper), mastiff(Clockwork),
riding dog(Clockwork), young dragon(Mercury), young
dragon(Mercury(!)), young dragon(Brass), young dragon(Copper)
Drow: All mounts except the juvenile dragon are celestial.
'bat'(Night Hunter)(UR), 'black dragon'(Wyvern), giant spider(UR),
pike spider (UR), psionic riding lizard, riding lizard, war lizard,
juvenile dragon(Purple)
Orc: All except blazing terror and winter wolf are celestial.
blazing terror, cave lion, griffon, horse, warhorse, dire cave lion,
dire wolf, winter wolf
A lot of the unridable stuff was fixed in between making this list and the current version, so most of those can probably be rode now. The lists themselves are still accurate, to the best of my knowledge.
As sorta' requested, fairly concrete stats on the animal companions/
sacred mounts templates. Enjoy, yo'.
The template never loses anything, so anything not repeated should be
assumed to carry over to the next level of CR bonus. Any displayed
bonuses are not cumulative -- that is, the +1 HD of +1 CR is not added
to by the +2 HD of +2 CR, rather the higher bonus overwrites the
lower. Generally, the CR increases when you gain a level. Sometimes,
it's every other level, sometimes it's not for a few. Paladins don't
seem to be able to get as high a CR bonus as druids potentially can.
Finally, this could probably all be summized somehow much easier. Oh
well.
NOTES: While testing, noticed a couple of things -- one, for humans,
unicorn was showing up as 'horse' in the selection menu -- probably
due to low knowledge or something or other. Eh. Secondly, drow are
_boned_ with paladin mounts -- about half of their sacred mounts are
unrideable, and, what's more, the nighthunter, pike, and giant spiders
(the unmountable ones.) all don't even get their sacred creature
template, just the celestial one. That's pretty harsh, yo'. Oh -- and
unlike animal companions, you can't see the sacred mount template in
the selection menu, just the celestial template. Made it harder to
check this all out, heh.
== ANIMAL COMPANION (Druids, Rangers, Perk'd.) ==
+0 CR
Adventurer type.
Regenerates 1hp/round.
Additional 60 ft infravision.
+1 CR
+1 HD, +1 Attack bonus, +1 natural armor, 105% speed.
Woodland stride.
175% movement when not ridden.
+2 CR
+1 to all stats.
+2 HD, +2 BAB, +2 natural armor, 110% natural speed.
Feats: Toughness.
Evasion.
+3 CR
+3 HD, +3 BAB, 115% natural speed.
+4 CR
+2 to all stats.
+4 HD, +4 BAB, +4 natural armor, 120% natural speed.
Feats: Knock Prone.
+4 devotion bonus vs Enchantment
+5 CR
+5 HD, +5 BAB, 125% natural speed.
+6 CR
+3 to all stats.
+6 HD, +6 BAB, +6 natural armor, 130% natural speed.
Feats: Power Attack, Multiattack.
+7 CR
+7 HD, +7 BAB, 135% natural speed.
+8 CR
+4 to all stats.
+8 HD, +8 BAB, +8 natural armor, 140% natural speed.
Feats: Improved Strength.
== SACRED MOUNT (Paladins) == -- Can't seem to manage to get a mount
with a +1 or lower CR bonus. Meh.
+2 CR
+1 Str, Int, Min Int = 6.
+2 HD, +2 BAB, +4 Natural Armor, 110% natural speed.
Beast type.
Evasion.
Magic Fang +1.
Regenerates 1hp/round.
Additional 60 ft. infravision.
+3 CR
+3 HD, BAB, +5 natural armor, 115% natural speed.
Feats: Toughness
+4 CR
+2 Str, Int. Min Int = 7.
+4 HD, +4 BAB, +6 Natural Armor, 150% movement rate, 120% natural
speed.
+5 CR
+3 Str, Int. Min Int = 8.
+5 HD, +5 BAB, +7 Natural Armor, 125% natural speed.
Feats: Trample
+6 CR
+6 HD, +6 BAB, +8 Natural Armor, 130% natural speed.
Innate spells: Command
+7 CR
+7 HD, +7 BAB, +9 Natural Armor, +135% natural speed
Doublepost prevention edit: I just confirmed that perked animal companion stacks with class granted animal companion. This is going to be an interesting run, huhuhuhu...