Whoo, boy, Starcraft...yeah. I think the AI doesn't cheat per se, it's just able to do 100-ish APM with a high degree of precision and almost no thinking time. In short, yes, cheating.
But as for my worst, I'd definitely nominate Worms. The enemy can pull of shots that should be impossible for any human. sometimes it manages to get a bazooka through a gap that's smaller than in. By using the wind to guide the projectile. Oh, and then hits your worm square in the body for maximum damage. But the bazookas are somewhat easy, they totally mock you with grenades. Bazookas miss occasionally, or at least don't inflict maximum damage, grenades almost exclusively do full damage when the AI is using them. To make it worse, the slimy bastards set up the timer and the throw so the grenade would explode exactly before it hits your worm, even if it had to ricochet one or three times beforehand. The AI is actively trolling with those shots. They suck with pretty much everything else but damn the bazooka and the grenade.
Also, Heroes 3. The AI is a cheating bastard it is. At least it's slightly more manageable...until you are hit with an army that you simply cannot counter even had you had awesome resource influx from the beginning.