Fiendishly difficult AI!: It cheats. A lot.
I'm not really aware of any other solution, unless you're dealing with a game that requires a ton of quick reflexes or something (i.e., the skill is something a cimputer is naturally much better at than humans without "cheating").
I think this depends a lot on the type of game we're talking about and what level you expect it to reach. I mean, for some types of games, like RTS games, the computer has the immediate advantage of being able to control many different troops at once and automate things better, but at some point an incredibly dedicated player will probably match that. Similarly, FPS games give the AI some accuracy penalties to see 'real' but eventually a player will be just more accurate than them.
I think Darkmere was referring to when games cheat in an incredibly obvious and OTT manner like in RTS games where the computer starts with many times more resources than you do.
An RTS game where all you need to do to be amazing is click quickly in obvious ways is not a good RTS game. In fact, it's not even really an RTS at all, since the "S" means strategy, and if you can win by clicking quickly with little advanced strategy, then it isn't one.
For example, I don't know much about RTS's but take Starcraft. The programmers program the AI to diligently build up a diversified army and then attack, or defend or whatever. If that were the only valid strategy, then it wouldn't really be a strategy game. It'd be a "click faster" game.
But players aren't going to fight the AI on that route. Since it does actually allow different strategies, they are going to decide decide "okay, they can click faster than me for building up a medium sized diverse army, so I won't win easily that way. Instead, I'll just zergling rush their workers."
I don't know if that actually works in starcraft campaigns, but you know what I mean. The AI strategies are relatively fixed (unless they're running crazy crazy technology on the AI), so if they click and organize at light speed, all it means is that you're going to lose for sure if you play their game, but you're going to win almost for sure if you strategize against their weaknesses. Which isn't a very good system. Because you figure out your winning methods in like, an hour, and then can just apply those ad nauseum (IF they aren't cheating)
If they cheat, though, then you might not only have to strategize against their weaknesses, but also do so very skillfully to overcome the pre-coded strategies + cheating advantage. AND you may have to switch to even better strategies if they cheat more and more in higher levels. Which makes the game more reasonably difficult and trains you better to be ready for human opponents and is more fun in general.