Regarding Paladins and splatbooks: Paladins get a lot of support in splatbooks, much more than Hexblades, for example. The options this opens up are actually quite good.
In Core only, the Paladin's class features do add up - compare a Paladin 5 with a Fighter 5. Paladin 5 isn't versatile in combat, but has options outside, can buff a bit, heal a bit, romance a bit, and has a mount to back him up. Fighter 5? Can trip or shoot things, and that's more or less it. Which the Paladin can do, too, if maybe not quite as efficiently.
Out of Core, Paladins get more class feature support through feats like SotAO and Battle Blessing. Those two combined make them better casters at least than Hexblades (whose spells are also severely limited, and who don't get new ones in each and every splatbook). Also, no class has more alternate class features in print, so there's a lot of versatility to go around. Some of these are very, very good: Harmonious Knight for excellent Bard-like Paladins, or the well-loved Mystic Fire Knight.
Also, don't forget some of the Paladin's greatest class features. Divine Grace is well-loved for a reason. Flat, freely stackable save bonuses are nice. Also there's Turn Undead. You won't actually turn much - but to power Divine feats and Devotion feats, this is essential. There's great Charisma synergy with some of these (Divine Might and Divine Shield, for example).
The diss Smite Evil got here is incomprehensible to me: There's Extra Smiting, Awesome Smite, and Ranged Smiting. There are, in a word, options for this feature. Options are good. And it's not as if a Paladin couldn't get himself a few Ordained Champion levels for more smite uses, too.
All in all, Paladins are nicely optimizable and offer lots of options. Most of these are probably best if you only dip 2, 3 or 5 levels. But more Pally levels definitely have more potential than, say, more Swashbuckler levels.