Well, I can see a Gnome Paladin, riding a Dire Fox, following one of the NG or LG gnome gods (there are lots -- see demihuman deities -- Baervan Wildwanderer, NG gnome god of animals, plants and travel; Baravar Cloakshadow,
NG gnome deity of trickery, illusion and protection; Flandal Steelskin, NG gnome god of craft and metal; Garl Glittergold,
NG gnome god of protection, trickery and illusion; Gaerdal Ironhand, LG gnome god of war and protection; Segojan Earthcaller, NG gnome god of cavern and earth). He would not be pompous like most paladins are, but would nonetheless fight evil wherever it lairs -- especially if this evil is common foe to the gnomes, like Kobolds, Goblinoids, or Giants. He would use humor and trickery as much as honor and loyalty during fights, and like all gnomes, would be wise and humble.
Furthermore, personnaly, I would also him to freely multiclass in Rogue or Illusionist (just like the FRCS allow some paladin order free multiclassing) without preventing from resuming progression as a paladin latter.
Here's my homebrew Dire Fox if you want it:
Medium-size Animal
Hit Dice: 4d8+8 (26 hp)
Initiative: +3 (Dex)
Speed: 40 ft., burrow 5 ft.
AC: 17 (+3 Dex, +4 natural)
Attacks: Bite +6 melee
Damage: Bite 1d6
Face/Reach: 5 ft. by 5 ft./5 ft.
Special Attacks: Leap 1d6
Special Qualities: Scent
Saves: Fort +6, Ref +7, Will +2
Abilities: Str 11, Dex 16, Con 14, Int 2, Wis 12, Cha 7
Skills: Hide 3 (+9), Listen 3 (+4), Move Silently 3 (+10), Spot 3 (+4), Wilderness Lore 3 (+4)
Feats: Weapon Finesse (Bite)
Climate/Terrain: Temperate forest and plains, temperate and warm desert (dire fennec)
Organization: Solitary, pair or family (3---6)
Challenge Rating: 2
Treasure: None
Alignment: Always neutral
Advancement: 5--8 (Large); 9--12 (Huge)
Combat
A dire fox attacks by by closing its target silently and pouncing on it with both forepaws.
Leap (Ex): If a dire fox leaps onto a victim during the first round of combat, it can inflict 1d6 additional damage from hitting its target with both forepaws.
Skills: Dire foxes receive +4 racial bonus to Hide and Move Silently.