In 3.5, they spread out the Paladin's powewrs even WORSE.
In 3.0, the pally sucked at level 3 also (because who gives a rat's &* about Remove Disease, and unless he's using Divine Feats, his sucky Turn Undead is almost a non-benefit.
Notice I'm ignoring his spells - for good reason.
Other than Level 5's mount, there's nothing for a paladin in 3.0 after Smite.
The real brutal thing about balancing a paladin that I haven't mentioned is: A Paladin is almost required to be a single-class character to be any good, due to all his abilities being level dependant.
However, the real kick in the nuts is that unlike a mage, the Paladins abilities are strictly linear (you notice I'm ignoring his spells).
So a Paladin, unlike any other class in the game, is the one that has the most restrictive roleplaying flexibility, has among the least multi-class flexibility, yet doesn't gain exponential benefits at high paladin levels.
If I could dream of a Paladin tweak, it would be that Paladins would gain kick-ass abilities at higher levels (drop the stupid spellcasting that's triply-handicapped: slow progression, crappy spell-list, and half-caster level) that would compare with what mages get at high level.
Give them enough power at high level to actually cause the EVIL forces to quake in fear at his presence - make him a legendary figure, make him worthy of tales to be sung for centuries, give him the ability to shrug off the worst spells that Evil can throw at him.
Give his sword the ability to cut thru a ForceCage, for example.
Do some damn work to make this game heroic, for god's sake, WotC!