Paladins are, at the highest levels, attempting to be recreations of Joan of Arc, King Arthur, and many other mythical and legendary characters of yore.
The best example of a Paladin however, is still Sir Galahad, son of Sir Lancelot du Luc. Sir Galahad was so damn fricking holy that he had the other knights in an awe, and they all just KNEW he was special. Not only that, he had an aura about him, that a Paladin's aura. RP it.
Paladins have a Aura of Courage, thats a supernatural, magical, constant effect that makes people braver. Can you imagine?
Kork the Cowardly wizard, trembles before the half orc bully. Suddenly, Justin the Just, Paladin, appears. He stands behind Kord, telling him to be brave, putting a hand on his shoulder. Suddenly, Kork gets a positive bonus to his Will Save, he feels braver. He stands up to the half orc and send him away.
Depending on how you RP it, that Aura could be nothing more than a plus to Will save
A tingling feeling on the skin
A feeling of holiness and rightousness
A choir of voices in your ears, bolstering you(bardic voices!)
Even a vision of the diety, telling you to be strong!
This is the same with Smite Evil.
Smite evil can be...
A plus to damage, nothing much.
A sudden flash of light as the weapon impacts, cleaving a deep wound into the orc.
A suddenly bright and glowing weapon, that cleaves harder and strikes faster for a brief moment.
The Paladin may suddenly look like a Celestial, complete with unfolding white wings and a radiant aura, just before he strikes you!
The Paladin may say something in Tongues, an unintelligible gibberish that strikes fear in your heart, causing you to hesitate, and the blow to therefore hit and bite deeply.
Clerics may be holy priests, but Paladins are the embodiment of a Dieties' will, the chosen warrior of choice in times of peril. Churches send priests to perform exorcisms. But they send Paladins to destroy and rout the physical enemies. They send Paladins to lead armies to victory.
Of ALL the classes in game, paladins are the HARDEST to play, the one with the MOST RP, the ones with the BEST RP, the one which is born to take part in RP Conflict, and one of the least powerful combat classes, and the one most likely to be killed or assasinated. In short, to be a paladin, you have a LOT of responsibilities, but very little backup. On most servers, Paladins are unsupported by DMs, resulting in much less of a holy paladin, and more of a Fighter with Religious Inclinations.
Also a problem with paladins is that its very hard to properly flesh out every church that comes along. It relies on the PC to come up with ranks, titles, more dogma and more rules, etc, to follow, for approval by the DMs.
It is HIGHLY unlikely, that a LAWFUL character would not know his position in the church, not have an official rank, and not know several standard prayers. I advise all paladins and would be paladins to try and liason with DMs before or after creating.