I think it would actually slow down the game and make it more static. Especially since, unlike 4e, 5e just doesn't have a strong 'forced movement' (shove is limited by size for exemple) and 'bonus movement' system in place. I think, rather than adjust AoO themselves, you should adjust the Melee classes so their AoO are simply better.
I've mentionned this before but:
Mage Slayer, Polearm Mastery and Sentinel all give your characters more trigger to your AoO, depending on the type of situation you want to specialize in.
I think that's something that could be integrated into the Fighter class, for exemple. Basically, customizing your AoO rules to fit your character. And add some of these to various monsters to make them more dynamic. That way, when you enter battle, you don't always know what the critters are capable of! You need to do a little prodding, maybe give the Fighter an ability that lets them analyze fighting styles to determine that stuff?
And melee characters could get extra AoO that don't use up their reaction. Maybe base it around Extra Attack? Every Extra Attack you get grants you 1 free AoO per round.
Feats in 5e being so much more valuable & rare than back when the tactical grid combat system was still in tact works against your case to bring up how feats can bring back some of it. It was still possible to build towards the "interesting build" niches you note, you were just good at it in ways that made you terrifying in your niche rather than merely capable. The problem with all the needlessly missing pieces is more the impact that it has on the tactical grid combat...
- The fact that the two example bodyguard types can be completely ignored in order to stomp the bbeg at the altar massively simplifies the encounter & dramatically raises the bar for what it takes to put some space between PCs & a baddie to force them to deal with the bbeg's minions washing out the story because anything shy of a huge group or a narrow corridor can be ignored at little to no risk.
- being able to reach into your pack to dig out & drink a potion as one action rather than two & have it no longer provokes an AoO means that there is dramatically less risk of over extending or waiting till the last possible chance before pulling the rip cord rather than pulling it because it's obviously going to be tight & maybe too tight or just being a little more careful about pulling a lerooyyy jenkins or just admitting "Yea I'm level 8 and those are only ten skeletons but I shouldn't risk getting trapped behind them & cut off from my allies"
- removing the AoO for reloading a crossbow devalues lesser weapons like the sling to the point of being nearly pointless
- so on & so forth.