Paladin Goblin needs Mount.

[Sor-El]

I have a Goblin Paladin in my campaign that worships Heironeous(may be spelled wrong)
He is a friend of the party that has the Complete Warrior variant levels.
Needs a mount.

[Fouredged Sword]

Riding dogs are good. Wolves are a little faster, and need not be evil.

[Kish]

Goblins riding wolves is as traditional as it gets, and a celestial wolf is an awesome mount.

[Gerrtt]

Your goblin paladin should ride in style, a monstrous spider mount should do nicely.

Or a dire badger. Or a wolverine.

[Hamste]

You should ride an ogre.


Assuming that is not an option, a riding dog is pretty good. You might also want to convince you dm to let you get a goblin dog. It's a bit weaker than a riding dog but the rash it causes and the hide is nice. Plus it is slightly faster.

http://www.d20pfsrd.com/bestiary/monster-listings/animals/dog/goblin-dog

[Flickerdart]

Using the guidelines in the back of the DMG, a paladin may call any appropriately-shaped creature with a CR of his level minus 3 (or -4 if it's flying) to serve as a special mount (with DM permission, naturally). What level is the goblin? I'm assuming 5, since he hasn't chosen a mount yet. In that case, Worg is the classic choice for goblins (just find one that isn't evil). Dire Badgers aren't as strong but have burrow, and Blink Dogs have Blink and Dimension Door which also grants them great mobility. However, Thoqqua are the best burrowers at that CR (20ft speed); the heat damage is a concern if the goblin intends to actually ride it, though. If you like the great cats, a Leopard can pounce and rake, making it a formidable combatant, and a Cheetah has a 1/hour charge over a ridiculous distance.

For pure combat considerations, Worg or Leopard are probably the way to go.