Which again, seems odd because the Cleric is the one that wields all of the divine power. Paladins are fighters with a little divine oomph behind them. You would think if either were chosen by the gods, it would be the one with divine magic coming out his earballs.
I'd guess it's all due to tradition and 'holy cows'. In AD&D 1e & 2e, clerics were considered the militant branch of the church. I believe the 2e PHB back then explicitly said they were, in part, based on the Knights Templar. All religions had clerics, partly because it was a dangerous world, and partly because it was (A)D&D. In 2e, the more scholarly type of priest would be represented by a specialty priest, who could have vastly different armour and weapon proficiencies, special abilities, and even a different spell list. This was, IMO, an excellent idea, but required a lot of work -- Forgotten Realms remains (to the best of my knowledge) the only official setting where every deity had a specialty priest write-up. It took two books (Faiths & Avatars and Powers & Pantheons), three if you include Demihuman Deities. This trio of books remains (again, IMO) one of the best sets of accessories released for D&D ever. It was not just the specialty priests, but detailed write-ups on
all faiths and deities in FR (even the dead ones... or the ones that were considered dead in 2e), including dogmas, clergy alignments, holy days, etc. If you can find them, the are a fantastic source of information, regardless of the edition you play in.
Later books introduced more priest classes, including the monk (a full spellcasting class that dabbled in martial arts (I remember unnarmed combat rules were... not very good in 2e)) and mystic -- both of which, IIRC, could fill the role of a more scholarly priest, but also the crusader -- a more militant type of cleric, again with full spellcasting.
I've heard paladins likened to special ops branch of the faith, and they were few and far between. This was mostly because of the (insanely) high requirements needed to qualify for the class (Str 12, Con 9, Wis 13, Cha 17, LG alignment and a bunch of other restrictions).
Not the best reasons, I'm aware -- just to show how previous editions sort of defined shaped the classes.