Hmm. Depends on the player, I'd say. Some people are intrinsically better at action games, others at strategies. Also depends on difficulty. For example, Doom 2 at its hardest difficulty (Nightmare?) was just insane. I think all comparisons should be made using the difficulty level for which the game was originally designed.

Chaos Strikes Back (Amiga / ST) probably gets my vote. Very tough without outside aid.

JA 2: Unfinished Business was plenty tough even on default difficulty. So was X-Wing, IIRC. Alien versus Predator was moderately challenging with the marine.

Can't really think of any truly challenging new PC games, though. Maybe Massive Assault (retail version); the AI in MA is very good. Certainly not Morrowind, unless you're playing a pure mage.