No way! I wanna keep my Paladins!
I so want to play a paladin when I get the chance.
A paladin will not attack a vampire who walks down the street, a vampire he knows he will lose against. He will get others, and come back later to fight the vampire prepared. However, if that same paladin encounters the vampire attacking an innocent, he would sacrifice himself that that person might get away. Because he is a paladin. He needn't attack things because they're evil headon. A paladin doesn't have to be an Aweful Good creton who goes around smiting everthing he comes across. Paladins can be just as Smart and Clever, if not crafty, and still be Honest.
Just like William Walice, who was Lawful Good. Sure, he was against the Laws of <i>England</i>, but he was Lawful to the People of Scotland, to the Ideal of Scottish Freedom, because the king was a cruel, LE ruler. What about BATMAN? I so want to play a Rogue/Paladin. He lives by his own code, but he does it with detective-work, with silence, observation, perception, loyalty to Law, and to Good.
Heck, A Bard/Paladin would be fun! (First is a Neutral good Bard, then shifts over to being paladin

.
Let's disect some more stuff, in FR terms.
The most obvious are the gods Tyr and Helm. Tyr is the god of Justice. His paladins are going to be your average ones. Helm is a god of Protection. If a paladin of Tyr and a Cleric of Helm are standing by a gate their lord swore them to protect, and a farmer passing by was attacked by orcs, the paladin would swoop in to protect the farmer while the cleric would be forced to protect the gate, at all costs.
Sune is the Chaotic Good goddess of Beauty, Love, Romance, etc etc. She can have paladins. A paladin of her would be a champion for Beauty. If something was defiling the landscape, the paladin would stop it. If something was corrupting beauty, like destroying artwork, they must stop it (A medusa turning people to stone, and then selling them as art?). A succubi using people's love and lust, an Enchanter playing with emotions, this the Paladin would uphold.
A paladin of Mystra, Goddess of Magic (Although she's NG) could uphold the Rightful or Lawful use of magic; magic being used to hurt others. A mage-hunter, if you will.
Heck, I could see a paladin of Eilistraee.
A paladin of Ilmater, God of Suffering, Healing, Martyrs, etc would be more for the relief of suffering, the Martyr to save those who cannot, or to releave the pain and misfortune of others, if that means his life.
I had a Half-orc paladin of Ilmater in my campaign once. He was awesome. Stupid as a brick, but a gentle soul.
Now, I think that some alternate paladins for different aligments, or a Champion of Idealism would be doable, and I'd like to see it. But really, leave the paladin alone.
There's much more you can do with them then 'EVIL! I smite you!' More like 'Okay, you're evil. Look, stop doing this. Okay, you won't, I gave you a chance to repent. Now, stay right here while I go get my friends, and we will return to stop you, with a vengence."