There are some great FPS's with amazing stories that make up a large part of the bedrock that is gaming as a cultural medium.
They are not retellings of the same story any more than Oscar-bait movies are retellings of other stories.
It's like saying "don't look at Harry Potter or Star Wars or Lord of the Rings as separate stories, instead think of them as different interpretations of the monomyth. It's the same story over and over, but if done well it can still be entertaining".
When all's said and done, I'd like to call them separate stories. Identifying the common plots and tropes doesn't make them the same at heart.
At the end of the day, your player has to PLAY the game and I guess I can understand the frustration of the grinding and the mechanic, but I fail to see what is superior.
Maybe people want more games like Heavy Rain? I loved Heavy Rain, it was an incredibly engaging and emotional story. I had a great connection with the characters and story, but there's only one problem: it's basically a choose your own adventure movie. Lots of watching, some playing, very little skill involved.
That being said, a great example of simple, (relatively) nonviolent gameplay giving way to countless hours of playing time is Minecraft. A Minecraft or even BridgeBuilder clone with this CryEngine would be pretty rad.
Edit - continuing:
Ico is fairly engaging and even intense in places, and it doesn't involve guns. Little flash games like N+ are actiony and you don't have to shoot people. I think a AAA high-budget game with N+ mechanics would be awesome. Darwinia is a good example of telling a story in a RTS.
Lots of games, even FPS games, involve stealth. So that's something you can do in an "action oriented, modern, gun-based game" other than killing hordes of random enemies. Another action-oriented mechanics is hand-to-hand combat, from realistic(ish) UFC fighting games to Ninja Gaiden or even Mad World.
([1] - We Can Remember It For You Wholesale, but everybody knows it as Total Recall.)