For me the paladin is something like a divine PR stunt. Or to put it less blunt, a rallying point for the forces of good and law under divine patronage.
This view was formed by some of the abilities seen on Paladins:
Inspiration: Call it auras or halo if you want to, but Paladins inspire those around them and grant them a strength they never knew. Around a paladin you're not easily shaken by fear, because you know everything will be alright. The forces of corruption can't take hold of a mortals heart as easily. The paladin literaly shines with divine light and upheaves everyone around, not through a spell, but by mere presence.
Charisma: To allow this inspiration, the paladin is a charismatic figure. If a paladin is present and doesn't actively hide himself, you know he's there. All eyes are drawn to him and even when he isn't active, he's the talk of the town (and kingdom, at higher levels). All to ensure his magnificient deeds don't go unnoticed, for all to recognize that no evil goes unpunished and the god bring succor to their faithful.
Righteousness: With all eyes on him and the ear of the people, the paladin accurately identifies and calls out evil in all forms. He doesn't just see some abstract evil, he reveals it. He can recognize the mark of evil and at his sword touch, the evil shapechanger is robbed of his disguise. As he goes through the slums, he sees who is to blame and who needs his help.
Healing: The paladin brings restoration to the sick, peace of mind to the mad and relief to those wounded fighting evil, at a mere touch. But all this could be done through spells you say? Perhaps, but to me the paladin is:
Not Spellcaster: The paladin has been permanently imbued with his abilities. He doesn't pray for them (though pray he does!), he does no invocations and no great gestures. To inspire, he just stands tall, to heal, he just touches and to slay the wicked, he just brings down his sword.
Smite Evil: The paladin is no preacher and no pacifist. Wether it is as a shining knight on the battlefield or as a prominent vigilante, who puts fear into the hearts of the depraved in a notorious city, he's a warrior. But it's not through supreme talent or training he puts down his opponents, but he overwhelms them with sheer righteousness. Seemingly untouchable, he simply clashes into his foes.
Immunity and Resistance: An important symbol of good, law and the power of gods, the paladin is not allowed to fall easily. As exalting as it is to see his deeds, as devastating is his fall. Thus, the paladin is divinely shielded. He never feels true fear and no sickness incapicates him. Poison has a hard team fining it's way through his veins and is mind is not easily subjugated.
Translated to mechanics, at the core, the paladin is a potent, but simple, warrior (no fancy maneuvers from class) with an emphasis on the charisma stat. All his abilities are either authomatic or recourced differently from spells He can heal a certain amount and as he gains levels remove conditions. He has immunities, resistance and great saves and can extend a certain amount of these to his allies via auras. These auras might also debuff opponents, as can his attacks (smites). As a topping, he gains some divinatory abilities. Not necessarily see evil, but the (limited) ability to see and reveal shapeshangers and illusions.
The paladin should share many qualities with clerics, they are both divine, but manifest them in a completely different way.