One game experimented with smart enemy units that could sneak up on a player and attack them from behind, or outflank them. The players hated it and assumed the computer was cheating and just spawning enemies behind them.

The same is sort of true in RTS games. The new rerelease of age of empires 2 has vastly improved AI that was developed by modders. Lots of players thought it was just cheating.

But in general it has been very well received. I think players can get used to good AI. They've just been trained to expect stupid AI that cheats.

For the vast majority of players it's probably irrelevant whether the AI cheats or not. The goal is not to play fair and beat the human usually, but to put up a good fight and make things challenging and, most importantly, fun for the human. Of course, competitive and professional players have different expectations or requirements in that regard.

Still, AI in games is mostly a trade-off. It usually can't take too much resources (because it usually has to run on the same machine the human is playing on), it has to be believable and fun to play against. This usually rules out too fancy algorithms and approaches with dubious returns.

I think the majority of players would prefer AIs that are challenging through better strategy and tactics, rather than just being bullet sponges or having better aim. People also get frustrated when the computer wins through cheating, rather than actually being better.