Nintendo shook things up by actually creating a brand new experience.
Now, it is harder to shake up the industry. Most things in specific genres are being done already. Stealth FPS. Check, start action FPS check, Single player driven FPS check, Multiple player only FPS check, Any theme you can think of, western, space, war, fantasy...check. There aren't many ways to shake up the FPS market.
Could Nintendo make a great FPS game Yes. Are there a few areas not yet explored with the FPS market...yes. But I dunno how marketable they are. I have my idea for the next big online game series, but it will have to wait...because I have nobody to share and work on the idea with....
Anyway, that was a totally different time period...and for the record the original Mario Bros...wasn't on a single console, it was on many, Atari, NES, Computer, Commodore 64 ect...