I still remember the mod scene in original StarCraft (+ Brood War) - it got to the point of supplying alternative AI algorithms, and there were plenty of non-cheating ones that were a noticeable step up in difficulty. At that point I already played competitively with friends and on-line, so they were only very challenging to me; for a new player, or someone casually doing the single player campaign, or just me a year earlier, they'd be impossible to beat.