So, any analysis of why People Think Paladin is Overpowered really has to look at the history of the class in previous editions. Cause, a lot of things "About the Paladin" are really legacy BS from older editions. Like, I keep forgetting that in 5E Paladin doesn't have an alignment restriction.
Mostly, also, I think it's because Paladin is really almost always better than Fighter, which is seen as a baseline character. A Paladin can really always do everything a Fighter can, while there is almost NO way to build a fighter to do what a Paladin does.
I don't know much about 1st ed, so I'll start with 2nd Ed.
AD&D 2E - The Paladin vs the Fighter.
At 9th level, the Fighter attracts followers. This is the ONLY thing Fighters get that Paladin's Don't.
Ability Score Requirements. Fighter, Str 9. Paladin Str 12 Con 9 Wis 13 Cha 17.
This of coarse back in the day when everyone always rolled stats.
So, if you got a really bad set of rolls, you could still almost always be a fighter, but in order to be a Paladin you HAD to have a really strong set of stat rolls to start out. A Paladin was almost always a better base character than anything else just because you HAD to have higher rolls to play it, Paladins ALWAYS had higher stats.
Then, on top of that, Paladins get a slew of other bonuses.
Detect Evil, Bonus to all Saves, Immune to Disease, Lay of Hands, Cure Disease 1/week, Aura of Protection, Turn Undead, Summon Warhorse, and lastly CAST PRIEST SPELLS.
All while still in Full Armor, using any weapon, and getting multiple attacks per round at higher level just like a fighter.
Drawbacks? Must be LG, Limited to 10 (permanent) magic items, can't keep money BEYOND WHAT IS NEEDED FOR A MODEST LIFESTYLE, PAYING HIS HIRELINGS, AND UPKEEP ON A 'MODEST' KEEP OR CASTLE... All the excess must be given to the church...
And a 10% tithe off the top of all treasure he gets to the church.
So, a massive upgrade over the Fighter for what are, frankly, not that big of a deal drawbacks. The access to the class by stat requirement is the real gate here.
D&D 3.X Fighter v Paladin
Same BAB, same Saves, same Skill ranks per level, same HP, same weapon and armor proficiency EXCEPT, Fighter gets Tower Shields Paladin does not.
The rest of the class. Fighter gets 11 bonus feats. That it.
Paladin gets Detect Evil, Smite Evil, +cha to all saves, Lay Hands, Party Morale Buff, Immune to Disease, Turn Undead, Summon Mount, Remove Disease 1/week, and Half Cleric Spell Progression.
Paladin Drawbacks: Must be LG, cannot associate with Evil Characters...
So, again, Paladin is a Fighter with BETTER STUFF. I'm sorry, you can't equal the benefits of Paladin spell casting with 11 combat feats. Let alone the other benefits the Paladin gets.
Pathfinder (D&D 3.75)
Built on the base of 3.5, Pathfinder made greater changes to some classes, but to fighter and paladin they kept the core from 3.5 and added on.
Fighter gets Armor Training, Weapon Training, and Bravery. Bravery is a save bonus against Fear, Armor training lowers armor penalties and increases Dex Bonus (raising AC), and Weapon Training (core) increases Damage and Attack bonus with groups of weapons. These are all decent bonuses, and we don't lose any feats. PF Fighter is just better than 3.X Fighter.
PF Pally gains Mercies which add condition removal to lay of hands, like you LoH to heal and ALSO remove Dazed or something. Also they now have a good Will save. They get a number of Auras at later levels that grant nice bonuses. The biggest thing however is the Divine Bond that replaces Summon Horse. Divine Bond CAN be used to get a special mount using the animal companion rules, BUT it can instead be used to have a Weapon Bond, that lets you enhance your weapon with magic power. So you don't need a magic sword, because you can cause your sword to be +1 for 50 rounds a day starting at level 5, and the bonus grows as you level.
Fighter does better here, but, again, SPELL CASTING, and the only drawback to paladin is having to be LG. The gap is narrowed, but Paladin comes out ahead. Now when you start adding in all the supplemental books, things get crazy (Fighter can spend weapon training to get a magic weapon power similar to Divine Bond, all kinds of other stuff).
But starting out from Core, Paladin was still slightly in the lead.
4e I've blocked from my mind and can't find the book, so I guess I'll skip that as well.
5E, Fighters get MANY lovely options, more extra attacks (3 & 4 per round at higher levels), and in general can easily match or exceed Paladins in really any field except healing. Also fighters get a built in self heal with second wind. Action Surge is incredible.
Fighter and Paladin both get extra Attacks, but Fighter gets more
Fighter and Paladin both get Fighting Styles, but Fighter gets MORE
Paladin gets spell casting, but a Fighter can go Eldritch Knight and ALSO get spell casting.
I could go on but I'm starting to lose interest in my own damn post...
To Summarize (TLDR): In Older editions the Paladin was Fighter++ with better stuff and super powers. In 5E they're Equal but everyone still remembers when Paladin was massively OP and it colors their opinions.