I believe thats the problem ... its a small difference.

I mean, if we are exchanging our personal deffinitions ...
I thought the difference is that Cleric is a person who have quite litteral link to his deity ... basicaly can talk to them (within reason ofc.)
While Paladin dont, and yet he sworn to devote his life to some standards his God / Goddess / or "just" some (not necesarily holy) Order he belongs to demands ...

Meaning source of magic for Cleric is his deity ... litteraly.
Source of Paladin is his own devotion "to the cause", whatever that cause is.

Thats why im not really sure if Paladins "need" a deity ... would be nice touch to have that option, no argues about it ... but i see no reason why Paladins couldnt simply serve some ... not really sure how to put it ... lets say Philosophical purpose, rather than actual deity.

Something like Paladins in WoW ... they worship "light" ...
Light in Warcraft universe is no entity (there are beings of Light, but that is different story), its more like type of energy they channel ... and they can channel it as long as they uphold some rules ... rules that can be twisted as wielder of that power see fit tho.

I still dont understand why cant we change Race for our hirelings. frown
Lets us play Githyanki as racist as they trully are! frown