And you're not going to get "beyond that" if the story itself has no impact on your decisions in the game. It's all still very linear.
And RTS games aren't linear? Hell, even most RPGs are linear. Games like Morrowind are totally open-ended (not really actually...you still have to go from A to B in the end), but most like Baldur's Gate and Planescape Torment are still quite linear. You can only go to certain places at certain times and in a certain order. I'm not sure we're anywhere close to the kind of development and technology it would take for a totally non-linear FPS. It would kick major ass, but can you imagine the size of a game like that? You think HL2 took a long time to develop...
And storylines just further your involvement in the game. If you want to just run and gun through a mindless shooter, that's fine, but most of us expect more than that from a game. I think the real innovation in FPS games is giving players many options to get past certain areas. For example, you could either sneak past a guy, shoot out the lights and knock him out, shoot him in the head, lure him into a trap, distract him by throwing something past him, etc. That makes games still linear (point A to point B) but gives the players freedom to 'do it their own way'. You can run through the levels and blast everything in sight, and I can take my time figuring out how to manipulate the environment to make the game more interesting. That was one of my major problems with D3. You could either shoot the demons or shoot the demons. I wasn't even given the chance to make the game interesting.
If we're going to make a story a sigificant part of the game, with resources spent on developing it, then make it more than fancy wrapping paper around my mindless shooter.
If a game gives you options, it's only a mindless shooter if
you play it that way.