Most games don't give you choices at all. Most are incredibly linear, even the good ones. HL2 had little to no choice. The most you could do was "walk around" an enemy. There was no element of stealth or choice whatsoever. FEAR, great game. Okay, run through hallways and blow away enemies. There were plenty of doors in that hallway, but only one could be opened by the player. No, today's basic FPS elements consist of: Cool graphics, badass or wise-cracking main character, fun weapons, and probably some kind of slow motion element. If you're lucky you'll have great voice acting, a wonderful story and excellent scripted action sequences.
GTA is one of the few games on the market that presents the player with any kind of choice. RPGs like Oblivion are by definition more open, but they are not close to FPSes.
Also, Vinny is right, it seems like SS2 again. In that sense it's really not that innovative, except for maybe far less linear level design. Oh, and the fact that nothing is scripted. But for real this time, not lies like that HL2 E3 video they showed us.
Bassoon, n. A brazen instrument into which a fool blows out his brains.