My wife plays a half-orc Paladin, and she deals out ungodly amountd of damage. She is the front-line fighter in our 20th level game. She's not so hot on the spellcasting and turning, but boy can she hit hard!
I played a halfling Paladin (one of two in that game) and they are surprisingly effective. Being able to have a Medium bonded mount works very well for dungeon crawling. Lance charge from dogback anyone? This would also work even better with a Gnome, I think.
I tried a Dwarven Sorcerer once. Didn't work well.
An Elven Monk works very well. The alignment means they are rare, but the Dex bonus is a great thing.
Half-Orc Rogues make great thugs. Give 'em a greataxe and flanking, and they can do icky things.
Half-elven Cleric. Everyone expects the Half-elf to be the loner type, a half-elf who spends her time healing and buffing others to try to gain acceptance could be interesting. Same for a Half-Orc.
Dwarven Monks could be frightening. The Dwarf stat penalty fits the Monk well, as does the Half-orc one, and the speed defecit is offset by the Monk class.
Just some ideas.
--Seule