Anyone who grew up gaming like I did expects the computer to cheat (or at least suspects it). Game development was a little different back then, and complex AI was impractical. To make up for this lack of sophistication, game developers gave the computer more resources and better "luck." I don't recall the exact numbers, but in warcraft the computer received almost twice as many resources as you did on hard difficulty (and still outstripped you on easy). Card games, like YuGiOh, were even worse. The NPCs seemed to always get the perfect combinations right when they needed them the most. Sure, some of it is paranoia, but that's healthy...but the majority of it is compensation for a poorly programmed AI.
Now, AI itself isn't exactly easy to program. Let me rephrase that, AI that is competitive and cannot be easily predicted (and therefore exploited) isn't easy to program. A great (if fictional) example comes from Star Trek, when Data tries to beat a strategy master at a strategy game. His first attempt is an utter failure, as Data tries to win an advantage immediately, and this is exploited by the strategy master bringing the game to a quick end. Data's second attempt involved him trying to keep even with the strategy master, and ultimately exhausting him until he quits.
This seems to be a good analogy for AI. The typical AI seems to approach a problem by brute force, overwhelming the player as swiftly as possible. The AI can only accomplish this by gaining an advantage over the player by tweaked resource production or a higher unit count (otherwise a player would be able to trick the AI and overwhelm it). A better AI would be able to implement complex strategies to try and outwit and outfox the player. If anything, it would just provide some more fun and variety to a game. At best, AIs in current games will randomly assign a "personality" and play that way.
AI is highly complex topic, and one I look forward to eventually designing myself. Hopefully, I'd be able to make one that didn't rely solely on cheating to win.