I guess what I liked about old school FPS games like Doom, Unreal, etc, is that I was expecting something akin to an arcade game (back then) and got a little surprise in that there were things to discover! Again, in Unreal, I could totally ignore the storyline if I wanted to. I have played it several times without reading a single message on a dead soldier's message machine or a single prophecy on the walls of the temple. And, yet, at other times I have read through the entire thing and let the "story" grab me a little. Now, admittedly, Unreal really didn't have much of a story. But that was part of its charm. You were free, as the player, to sort of imagine a bit here and there.

The pleasure in Unreal was the unexpected. For example, in the first level, you come to a door you cannot open, but it is obvious that you need to go through it. You hear the screams and the sounds of the creature attacking. The door starts to open in time for you to witness the dead and the monster running. So there was a little drama. Later, when you finally exit the ship, you are treated to an absolutely stunning outdoor scene (for the day in which this game was created)! The turbulent sky, the chasm with the river at the bottom, the waterfall ... it was a great contrast to the interior of the ship, which was a fairly typical RT3D type environment. Every so often Epic threw in a curve to keep you entertained while leaving the basics of an FPS completely intact. It worked!

I have not played CoD4 or Far Cry. I did download and play a portion of the Crysis demo. Crysis was beautiful to see, but it was the same old, I am a pawn to the story stuff. I don't play it. Co4D sounds like fun, but like Quake 4, it does not really strike me as an FPS (from your description). It sounds like someone was trying to mix a bit of a strategy game in with an FPS. If so, things like this are done all the time ... mixing genres to see what works.

I guess the old school in me is a big advocate of the standard fare FPS, but I also want to find a way to make the standard FPS unique without detracting from it. System Shock 2 did this. The found a good balance between making you a slave to the story and letting you play a standard FPS.