You Can't Nerf and Respect at the Same Time
How can I best keep the fights interesting while respecting their character creation choices?
Essentially, you cannot. You're asking for, in essence, "What is my next step in the arms race?"
If you have a party of the expected level and number of players, you don't need any rebalancing to accomplish interesting.
Attempting to ratchet the difficulty up is inherently not respecting their build choice
Increasing the Attack Bonus
This is the most obvious disrespect of the choices they've made. It's an outright negation of their choice.
Modify the Encounters
This is more of the same - tho less egregious. But it's the same problem - you want to take away the advantage they paid for in feats.
Disallow Moderately Armored
This also is disrespecting their choice. You seem to have already figured this out.
Interesting ≠ More Difficult
An interesting fight isn't of need more difficult. It's often non-combat stuff that makes it memorable.
So What To Do?
Use what's there better. Assuming you're running a party of the correct levels (IIRC, it starts at 3rd for the non-encounters version), and have only 4 players, the encounters are balanced. So it's time to use what you've got.
And what you've got are a bunch of nutjob cultists. Have them making brash assertions of skill. Have them use group tactics and the 3rd dimension well. Make use of the terrain. Use the multitude of "save or suck it" spells (like the create bonfire cantrip).
And above all, describe, describe, describe. Don't say, "Cultist 1 attacks Player 2." Do say, "The tall cultist is attempting to impale Fredo upon his spear." Things will get a lot more interesting and memorable just by describing better.
Mechanical Stuff to use
There are a number of mechanical options that can increase the risks to PC's without disrespect...
Give monsters their death saves. This really does make for some tense moments.
Remember to use cover and consider using flanking(DMG optional rule, p. 251). If the ranged attacker (spellcaster especially) doesn't have line of sight to all 4 corners of the target's square, the target has +2 AC (partial cover). If only one corner can be seen, it's +5 AC (3/4 cover).
Use the Lingering Injuries option(DMG, p. 272). Makes crits much nastier.
Yes, the jump is the distance from the ground to the bottom of your feet
When you make a high jump, you leap into the air a number of feet equal to 3 + your Strength modifier [...] Either way, each foot you clear on the jump costs a foot of movement.
Intuitively, a vertical jumping distance makes the most sense as the distance between your shoes and the ground but really your entire body is moving the same distance upwards. The rules' language talks of the distance you "clear" and "leaping into the air" both of which evokes the imagery of the gap between ground and shoes. More direct evidence can be found in the following passage:
You can extend your arms half your height above yourself during the jump. Thus, you can reach above you a distance equal to the height of the jump plus 1 1/2 times your height.
So it is clear from the rules that when you jump, the distance is measured from the ground to your feet and that means that the rest of your body moved vertically that same distance.
If the PC can jump X feet, their feet reach X feet
If a 6' tall character jumps up 8' it means that their feet are 8' above the ground and their head is 6' + 8' = 14' above the ground. If they raise their arms the tips of their fingers would be 1.5 * 6' + 8' = 17' feet above the ground.
In this case, if a character jumps up at a 8' wall with a jump of 8', then the assumption is that they land on their feet on top of the wall.
The way the jump looks narratively is not defined
How all this jumping and leaping looks is completely situational and also not at all defined in the rules. In cases like these, the DM must fill in the blanks.
Best Answer
AC is only one form of defense, and doesn't typically grow with level.
What you're running into is the concept of Bounded Accuracy. One of the design pillars of D&D 5e is the idea that even high level characters don't have passive defenses that make them invulnerable to the attacks of lower-level characters. It is an intentional feature of the system that level 1 characters with an attack bonus around +5 can hit the AC of a level 20 character.
What this means is that, as characters level up, one of the ways that they get more powerful is that they hit more often, and are hit more often in turn. It's totally normal for most attacks to hit in a high-level combat where everyone is swinging with attacks above +10.
Generally speaking, without magic items, the highest AC a character can reach is in the low 20s. A paladin with a shield wearing plate armour isn't going to go much past 20 without magical assistance. A breakdown of how a character hits maximum AC can be found here. In short: Barbarians can get their AC a little higher than 20 without magic because of their higher stat cap, and magic item can push your AC another few points.
What you're missing is the other kinds of defense that make a high level character hard to kill. Higher level characters have many more hit points and access to defensive buffs than low level characters, and generally have more passive and active defenses in general. For example: your Paladin player will eventually get an aura that protects the party from various effects, based on their Oath. Also, Lay on Hands acts as an effective HP buffer that makes the party much more difficult to take down as the Paladin keeps them healed. In addition, your casters likely have a large number of battlefield control spells that make it possible to shut down enemies before they can even attack at all.
Your players probably won't have their AC increase, but they will get many more ways of dealing with threats defensively.
Note: The link to the Wizards article on Bounded Accuracy goes to the Wayback Machine, because the original article is no longer on the WotC site.