I'll take a different tack here.
I have played paladins and for roleplaying, they rock.
But sheer power?
They are the most over-rated class of all, power-wise IMO.
Everybody points to spells and smiting.
Sorry, smiting evil ONE TIME per day for only +level damage IF it hits is way too weak to even consider highly.
Spells REQUIRE the paladin to be single class, and other than Divine Sacrifice and Bless Weapon (the latter only in special cases), he gets almost nothing until Holy Sword.
And he casts as 1/2 his level (which i think is a terrible double-penalty), so the spells are even weaker.
Power analysis:
Smite is too weak, Turn Undead is worse than cleric, Detect Evil is kinda an annoying, mostly-roleplaying benefit, Remove Disease is a joke, Mount is nice but takes a lot of levels, and Divine Grace is very good.
Conclusion:
For heroic gaming (i.e. a powerful PC), I have switched to playing Cleric/Fighters. If anything, one level of paladin gets the best of the class features.