I'm not crazy sold on it. A paladin isn't just a fighter/cleric. A druid is not just (or even?!) a rogue/cleric. A ranger is not just (or even?) a fighter/rogue. They should be able to do their own things, in their own unique ways, without defining themselves as handy labels for multiclass options. ESPECIALLY if players disagree with their multiball categories.
What can a paladin do for me that a fighter/cleric can't? Because I think there should be paladins, and they should be unique as a class rather than just combos of other classes.
But, the paladin is, to a certain degree, a combo of fighter and cleric. It shouldn't be JUST that, though. Otherwise, why make it its own class?
I guess I'm pretty strongly of the opinion that something archetypically powerful enough to have its own class (like a paladin, but not like a mystic theurge) is probably worth a unique expression of that archetype, not just a kludged together amalgam of other classes.
It is funny that back when they were working on 4e, they had this similar confusion of what is a Paladin compared to other holy warriors.
Personally, I took the Paladin to be the 'Divine Champion' of a holy power. The Divine essence (even if it is a small fraction) invested in a mortal shell.
A prophet might speak the words for a the divine to give instruction but a Paladin/'Divine Champion' performs actions for the divine.
This is why in 3e they 'glowed' so much brighter than a Cleric who simply choose to work for a divine power. The Cleric chooses an association and performs the duties of that association. There are often hundreds of clerics/priests for every one paladin.
Look at the movie Van Helsing. There is a full organization of holy people willing to support Van Helsing but only one Van Helsing willing to take the fight into the monster's den.
Loot at the arthurian knights of the round table. There were many knights but only one of virtue to sit on the seat perilous and bring back the grail. Any other who would dare sit upon the seat perilous would be struck down by the divine for the afront.
Many a cleric goes their entire life without ever really being in contact with their patron God. They work without the assurance of the divine being there since they've never personally been touched by that spirit. They see their spells work but wizard spells work too. There are plenty of agencies like angels and outsiders that could be providing the power to make a spell work.
A paladin has that inner contact that tells them that the divine is with them even in the darkest and remotest moments of their life. A paladin 'falls' when they lose that thread of contact and it often drives them insane to lose that contact. They lose their moral compass and wonder as to where they can go afterwards after that moment.
---------------------------
Game wise, I'd have Paladins have more a 'miracle' feel instead of a 'spell' feel. Lay on Hands is the perfect example. It happens because of the divine contact without any pleading required. Paladins have plenty of things they should be able to do with just the will to do them. Paladins of a higher level should have angels coming to their aid because they are the 'heroes' of their gods (like a Perseus or Odysseus).