FPS games are definitely becoming stale to me, at least with multiplayer. BF3 almost perfected the art of the multiplayer shooter IMO and I don't see where it could possibly go from here. Don't even get me started on military shooters.
Maybe the industry could take a clue from games like Timesplitters and throw realism out the window for a second. Even so, there's way less possibilities and stories that can unfold in multiplayer compared to singleplayer.
Take this game for instance. It's an FPS, but instead of holding a gun, you're holding a camera. Very unlikely candidate for a multiplayer game, yet a potentially awesome experience nonetheless. Is this game in demand, though? So many people complained that MW3 is a rehash, but they're still buying the game. They're voting with their wallets.
I have a friend who buys FPS games mostly for their singleplayer modes and he's expressed a lot of disappointment with games that have like 6-hour campaigns. What happened to SP-only games like Bioshock? Like you said, the storytelling in most modern FPS games is subpar, and I only hope devs start realizing its importance—even in multiplayer.