I think Sid Meier said something along the lines, that an AI should not try to copy how a human would play but provide some kind of steady resistance. More like a force of nature for the player to overcome than a real opponent.
I think Starcraft and other RTS games are good examples of games that often have both modes of AI. Skirmish AI games are attempt at mimicking human opponents, and provide for reasonably good multiplayer practice. Campaigns create a steady resistance for the player to overcome.
In 4X games and RTS games one issue with efficient AI's that don't cheat, is that they are ruthlessly efficient at economics and micromanagement but very bad at actual tactics and strategy. That results in some rather odd gameplay.
There are so many ways to create AI opponents and the best approach very much depends on the specifics of the game. Generally I'd say that it's fine if an AI cheats as long as players don't notice too often. But the more transparent the game gets the less cheating is possible.
When developers create computer opponents that cheat, the purpose is to make the challenge more fun. And this is the core of the issue - what kind of AI behaviour and game balance is fun.
I think it's important to have computer opponents that acts in a way that makes sense for the setting and helps immersion. In many cases a computer opponent is more like an actor or game master than a real opponent.
I actually think the worst part of cheating is when I get the feeling that the AI or the game is letting me win on purpose. Scaling difficulty is one of the worst mechanics in this regard, because it takes control away from me as a player.
Then you have games such as Rome: Total War, where increasing the difficulty doesn't make the computer a better strategist. Instead, it turns your army into a bunch of wimps with less morale and fighting ability.
I don't know about Rome:Total War, but in some strategy games it feels like that because lower difficulty levels give the player overpowered units and then even out the difference at higher settings. Sometimes making the computer a worse strategist can be even harder than making it better. Inverse cheating happens very often.
I like when a strategy game shows the baseline setting, the one where neither the player or computer is given a handicap. That makes it easier for players to decide if they want to put the difficulty slider above or below that baseline.