Ah, the Pally. I'm going to have to award +5 courage points to the OP for having the guts to start a Paladin thread.
Like
Smite Evil--It's just fun to blast bad guys with it.
Lay on Hands--Good, balanced healing power that isn't spellcasting based.
Aura of Courage--I have to agree with whoever first said that Paladins should have more stuff like this.
PokeMount--By golly, "I choose you, Horsey-chu!" is more fun than "Ah, Intrepid Companion, my equinary soulmate! It's so good to see you again. Shame you couldn't come with me on the perilous 47 layer dungeon of 503 narrow staircases! Or the Caves of Uneven, guano-coated sliperosity....or that mountain climbing adventure...or flying to the cloud giants castle....the plane of water....anyway, I hope you're well fed, yes? The Pally petting zoo is fast becoming an important source of income for the local charity, so at least you're still fighting for the side of good...in your own way. Have another processed lump of hay that smells like an apple."
Course, I've never been a big horse person anyway, so I have no problem with upgrading to a pegasus, griffon, celestial charger, or whatever it takes to make the ability more acceptable to people. (In the sense that a more magical mount is easier to make "magical")
Divine Grace--Having super-duper saves helps give the Paladin a viable niche, and fits well with the class.
Don't Like:
Cure Disease. I mean, whatever, I'll take it...but shouldn't this just be on his spell list?
MAD--Next to the Monk, the Paladin always feels stretched too thin. Maybe make his abilities pure charisma based?
Spells--I don't actually mind the spellcasting, but the current spell system for Paladins and Rangers lacks oomph, which is generally made up for by giving them OP spells for their level, just so they have something worth using. And the half-caster level thing doesn't work that well, either. Could probably be done better.
Code of Conduct. Now, I've never played in a group that was that tough on Paladins. But based on the hot-blooded arguements I've seen on various boards, I'm thinking Wizards needs to put out some sort of explicatly lax code. Lots of lots of "Paladins can...." statements, instead of broad negatives. (In 4.0, Paladins totally like to get rip-roaring drunk and dance on the table with panties on their heads!) Something to break the Lawful Stupid stereotype in half.