StarCraft
It's been a real trip. Aside from that one mission where I had to sneak Tassadar through a Terran installation (with all the retries it must have taken me nearly 3 hours), I never found the campaign frustratingly hard, but at the same time it was usually satisfyingly challenging. The final mission might actually be regarded as easy, but it was still way fun.
Props must be given to Blizzard for giving a strategy game a good story, when it would be just as easy for it not to have one at all. Granted, it doesn't have the full effect unless you read the supplemental material in the game manual, but the way it flows into the campaign missions is superbly done. When combined with never-ending online multiplayer fun, and a reasonably robust map editor, StarCraft is truly a classic game.
Progress: Finished campaign, no cheats!