OP's feelings that constantly missing for 0 damage is not fun *is* a valid criticism and valuable feedback. If they are not having fun, then they are not having fun. Period. They should be able to play a game where they miss less, and others should be able to play a game that holds more strictly to 5e rules.
This would be sooo easy to implement using different difficulties:
1.) Story Mode: Enemy AC and Saves are reduced by 5 across the board. Weight player dice rolls (e.g., always roll another d20 under the hood and use that if higher). Allow all the opportunities for advantage that are currently in the game.
2.) Normal Mode: Enemy AC and Saves are reduced by 2 across the board. Height and backstabbing still give advantage, etc. Implement pseudo-randomness, where rolling a number makes it less likely to be rolled next time.
3.) Hard: Play the game using 5e RAW, except still allowing height gives +2 to attack. Maybe leave in backstabbing (or flanking) but as +2 bonuses. Shove and hide are normal actions. Jump provokes AoO. No dice-weighting.
4.) Tactician: Enemies are stronger, +HP, +AC, +Saves. (Importantly, to preserve class-balance, any AC change also has to affect Saving Throws)
Alternatively, an even simpler solution is to adjust only enemy AC and saves for each difficulty level. If you're frustrated with missing too much, you should be able to drop down a difficulty level and hit more often. But this still allows players who want to play 5e RAW to play 5e RAW.
