MHO: most intellectually challenging has to be an RTS. It has not just to make you think, but make you think quickly. And expand your memory banks, and make you store away and recall loads of information on-your-feet.
It's just hard to think which RTS did that. I used to play 8 AI's in Red Alert 2, which did it. Rise of Nations (which is basically the RTS version of Civ) had quite a number of stalemate situations, where there was perpetual combat; but even as you are trying to micro that, you have to come up with an overall strategy to break the stalemate. Sins of a Solar Empire 4-way multiplayer was very intellectually stimulating.
That raises a good question for me though. In RTS games how much of it is best inference under time constraints and does that qualify as intellectual?