My play experience is that the paladin doesn't perform too badly, at least at the lower Heroic tier. I've personally run an elf paladin with relatively balanced stats (Str 14, Con 13, Dex 14, Int 10, Wis 15, Cha 15 at 1st level) to 6th level, and he was certainly able to pull his weight in a fight.
Of course, I did focus on attacks with the weapon keyword that targeted a non-AC defence, such as piercing smite and invigorating smite, so I was able to maintain a pretty good hit chance with those powers since I got to use my weapon proficiency bonus, but only needed to hit a defence that was usually lower than AC. Radiant delirium is also nasty since whether it hits or not, it's pretty much a guaranteed daze for one round.
The paladin's minor Leader abilities and powers such as lay on hands, channel divinity: divine mettle and wrath of the gods also mean that he can do more in a fight than simply dish out damage. If you enjoy playing "helpful" characters, that's another plus point for the paladin.
My only real gripe about the paladin is that the 2nd-level utility powers aren't that impressive. Getting your Wisdom bonus to Fortitude (in the way that some Primal classes get their Constitution bonus to AC in light armor) or finding some way to use Strength with divine challenge (perhaps if your challenged target makes an attack that does not include you, you can shift 3 + Charisma bonus squares and make a melee or ranged basic attack against it as an immediate interrupt) would be nice, but not really necessary, IMO.