Wow, all good suggestions...

I'd like to add Darwinia to that list 'tho - I can't think of a game so simple yet so complex... it's almost Tetris-like!
I just played the Psychonauts and that's pretty fun. Damned well should be since it was made by the same guy who was largely responsible for stuff like Day of the Tentacle

However, there is a fairly strong 3D platformer element which may put people off. Basically, if you hate MDK, then you'll hate Psychonauts because they play *very* similarly.
The Warhammer game, Dawn of War is very good too, but the single-player mode is depressingly short.
If you're really stuck, get a SNES emulator and play ChronoTrigger - Best damned game Sqauresoft ever made IMHO.