You know what I think when I think Paladin? The questing knight.
So I'd like to see the Paladin as a Knightly type. He's got the skills, the heavy armour and martial weapons. He's got some access to the martial action system. He might have minor devotional powers. But when he swears himself to a quest, that's when the good stuff happens. Mess with the Paladin personally and that's one thing, seek to bar him from the object of his quest and that's when he gets that holy fire gleaming in his eye, that's when fate guides his hand and honor shields his soul.
DING, DING , winner!
Paladin class is inspired by the French, Gnostic inspired Courtly Love chivalry .
Nothing better epitomizes the essence of the genre than the questing knight.
The great thing about going that quests route is you can switch up themes.
Tristan, of Tristan and Isolde is a Knight of Love, - UNSTOPABLE.
In the tale of course his true love is betrothed to his King, and he steals her for a time, and is still in effect a Paladin, in defiance to his king and with the kings woman, because his love is pure.
I'd play that.
There are Paladins of justice, righteous war etc, and you could even allow changes in theme with different quests (if you want). The Champion class from Arcana Evolved was very modular, and very flexible in terms of concept.
I'd rather more abilities, and less to no spells.