Syngod: If you're looking into a real challenging strategy game, take a look at Caesar III.
It's more like Sim City but at some point during the game you can control your army. And there are a LOT of things to do to please your citizens.
Maybe you already know this game, I know it is quite old, but it's very challenging, to me that is.
Then again I never completed Warcraft II :p , don't laugh !
I know someone who was really good at Sim City 2000 and that has a hard time getting past the early levels of the game.