This wasn't an issue in 3E/Pathfinder unless a guy built for AC. The paladin is not building for AC.
Just being a Paladin is building for AC.
Seriously, though, ACs in 3.x, IIRC, tended to be mostly pretty low, relative to the 1st iterative attack of a full-BAB PC or a same-level monster (and heavy armor AC irrelevant to touch attacks), instead serving to let you focus on stats other than DEX, and to avoid being hammered with multiple hits from full attacks.
5e is completely different, AC from heavy armor is not a poor second choice (though, really, with DEX such an uberstat it's still not exactly optimal). That harkens back to classic D&D, where being able to use better armor really was a meaningful advantage.
So far it has been the case with any heavy armor and shield user. Plate armor, shield, and defensive fighting style, all obtainable very early on, gives an AC of 21. Your average rogue with an 18 dex has an AC of 17. Your average caster with mage armor and a 15 or 16 Dex has an AC of 15 to 16.
That still sounds better than 1e, when a 1st level fighter might have an AC of 3 or 4, easily getting a 2 when he could afford plate-mail, before DEX bonus (which worked with any armor, and might give him 0 or even negative AC, the equivalent of 21 or better in 5e), vs at best 4 for a thief (18 DEX), and likely 10 for a magic-user (or up to 6 with DEX bonus). Actually, that really only sounds better for the wizard, now that I type it out. For the Fighter, Paladin or Cleric in heavy armor, or the Rogue in leather it's about the same.
Chalk up another classic-D&D-feel success for 5e!
Casting that one spell takes up 25% of his 1st level spell slots.
Compared to 100% of your 1st level slots in 1e.
These types of AC discrepancies weren't quite as large in 3E/Pathfinder largely due to easy access to disposable magic items allowing mage armor to be cast without expending a spell slot and shield lasting an entire combat.
Defenses in general were in a tighter range in 4e, too.
I find it surprising and problematic because it did not work the same way in previous editions of D&D.
5e harkens back more to classic D&D, in letting armor actually be a real advantage (it could have gone further, and let DEX add to AC across the board, perhaps with some sort of STR min required, instead of limiting it in medium & heavy armor) for the classes that get it automatically. Bounded accuracy means that a higher AC really is higher, rather than just being slightly ahead of the curve, and needing to be kept maxxed to maintain any advantage.
It's kind of a unique element of the idea behind Bounded Accuracy I'm running into as a DM. That's why I mentioned it. It didn't work this way in 3E/Pathfinder. I'm wondering if many other DMs have run into the situation.
In classic D&D, heavy-armor classes would start out pretty hard to hit, and, as their hps increased rapidly, become easier to hit. I haven't quite seen that in 5e. I haven't had anyone in plate yet, and have seen more impact, at first level, from variant humans with DR from the heavy-armor feat, than from high AC due to heavy armor. ACs seem to have mostly been in a tighter range than you've seen, with lighter-armor types consistently having good DEX, and heavier armor types consistently in chain. But, I have run very low level games (1st-4th), with very little treasure, either monetary or magical, and AC does seem to be very equipment-dependent.
Paladins are not invincible. My concerns with their power is the breadth of it. They can deal with a wide variety of situations no other martial can come close matching.
I don't know if I'll ever get used to the way you use 'martial.' Paladins are divine champions wielding overt magic direct from the gods. They may also use martial weapons & armor, but that's like calling a jet an automobile because it has wheels.
Last night I threw a hydra at a party of 6th level PCs. They destroyed it. I boosted its hit points 150%. It was very easy to kill the heads and apply fire damage to prevent it from regenerating. They also fought two treants with four animated trees. They beat that easily as well. Fire damage very easy to come by. Even with damage resistance, two treants couldn't dish enough damage to seriously threaten the PCs. Minimal resources expended to kill them. It's so easy to beat regeneration in 5E that it is a mostly useless ability.
I was hoping with Legendary Actions and Lair Actions solo monsters would be stronger. They aren't. A party with an average of two attacks and focused spell power can't be matched by a single creature even with Legendary and Lair actions.
I wonder if the intent was such an easy game. I'm going to have to figure out how to rectify that. I don't like a super easy game.
One aspect of 5e's 'fast combat' emphasis is to make combats tend towards being one-sided. If you're going to win, you're likely to win quickly, and the enemy to inflict minimal losses on you. If you're going to lose, you're likely to loose fast and completely - unless the DM starts soft-balling things (which, isn't ideal). If you've got some basic system mastery and tactical know-how going in your party, and you don't overwhelm them with numbers, it's likely they're going to win, and a lot of those wins will seem very easy.
So, yes, the intent was such an easy game. But, you can tune it as you like, either carefully with trial & error leading to re-built monsters and/or other sorts of detailed prep, or on the fly by feel & experience.