Im not a huge fan of FPS so my idea doesnt center around a story. After all you do in an FPS is run around and shoot things (basically,) and, yes, there are better versions of running around and shooting things, but that is still esssentially what you are doing.

Players characters are fully customizable. Players define various specs: health, speed, base armor, sidearms etc. Each has a nice balance of pros and cons (eg. more health mean you have a bigger character which in turn makes you a bigger target.) All in game weapons are defined on a series of characteristics:

rate of fire
heat generated
clip size
etc

and their ammo is similarly defined

damage
accuracy
area of effect
etc

Players mix and match these options with similar balancing issues (high rate of fire but also high heat.)

The story goes like so: you are a (space marine/detective/blah) and your goal is to (save/stop/kill) something through different levels...with a killer instinct.

Anyway, I think it would be fun to have the player define their own weapons. I could have a two-handed machine gun with heat seeking rounds and the next time maybe I want a laser guided rocket launcher.