Depends on the edition. In 1e, the cleric was the warrior arm of the church and represented them in the field. Their inspiration was explicitly drawn from Knight Templar and their ilk. Paladins were the knights in shining armor whose virtue was such that God favored them. Despite the officially polytheistic assumed setting, the archetypes were still drawn from Medieval Christendom.
In 2e, the cleric attempted to take a desk job and the paladin had to pick up the slack (which he did poorly, IMO). The clerical mechanics reflected polytheism much, much better, but could be unbalanced in practical game play (i.e. it was possible to build both a cleric who wasn't jack as an adventurer and one who was still a Templar).
In 3e, neither class really figured out which mold they want to fit. It was at least implied that paladins were semi-ordained holy warriors. But, clerics were still battle-ready priests who easily outclassed any purely mystically focused breathren.
I haven't played enough 4e to tell you for sure, but it seems the 3e schizophrenia has been carried over somewhat. It seems better, but still present. This is probably because of the explicit focus on combat ability, but I'd prefer the cleric to straddle the leader/controller line more than the leader/defender one. Maybe we'll get a "priest" class later that does just that.
On a similar note, I could see the favored soul reappearing as divine striker. I wouldn't expect wings (which is a good thing IMO). Rather, I'd expect it to be the answer to the question "What would a warlock look like if they made a pact with a god or angel?"
