I personally consider the following to be most demanding on my skills:
Operation Flashpoint (the first one)
S.T.A.L.K.E.R.: Shadow of Chernobyl
Red Orchestra: Ostfront 41-45
SWAT 4
In more conventional shooters like, say, any Call of Duty game, I find myself "running on auto-pilot" so to speak. What (relatively little) challenge there is is not in knowing what to do, but rather just doing it and, if you fail, doing it slightly differently. In single player, for instance, this involves picking the right moment to push forward, when you've worn the stupid respawning enemies down enough (and in the right places), and being lucky enough to avoid the enemy nadespam...
There's not much else to it, really. For example, you rarely if ever even have to navigate because you're usually being led around by the nose and have no responsibility except to shoot things and, occasionally, press F to initiate scripted sequences when someone yells at you to do so.
Obviously I'm referring to single player Call of Duty. I did find Call of Duty 4's multiplayer to be pretty challenging (at least, on the PC a couple years after the game's release, which invariably means playing with a bunch of people who've played it a lot), but not in a very satisfying kind of way. As long as you understand the game modes and know the maps reasonably well, you still don't have to put much thought into what to do (beyond choosing your kit...), just how to do it as effectively as possible.
In a game like Operation Flashpoint, by comparison, knowing what to do is just as important as knowing how to go about it, especially if you're a squad leader. In Flashpoint, a lot of missions dole out a few objectives, then give you a squad, a few vehicles and some support elements and leave you to work out the rest. And "the rest" is a lot of things. For instance:
* Conducting reconnaissance.
* Deciding which direction you should approach your objective from (and how you should get there in the first place)
* Deciding which weapons your men should use (and putting them in the right places so they can make best use of them)
* Adjusting your behaviour and that of your squad to suit the situation (For example, to hold fire unless attacked to avoid unnecessary attention)
The result is a very difficult and challenging game; but a game in which, quite often, you're killed because you made an error in judgement that put you in a particularly dangerous (and usually avoidable) situation, not because you just got blown up by three laser guided hand grenades thrown into the narrow corridor which is your only way forward.
