Gun on the PS2 was an absolutely quality game...it was so badass you could ride your horse to death! Literal death!

What about a space western mercenary game, where your goal is fly around different planets, take jobs and smuggle stuff? that would be cool too.

That would pretty much be firefly the game, huh? Your signature makes me sad, Colonelstubbs.

Sorry...i just need to see the crew to remind myself they existed. Goddamn you Foxnetwork!

people forgot to mention the father of non-generic FPSes
warren spector is the FPS master, people, and other than HL1,no other FPS even comes close to spector games in measures of quality or originality
so yeah ,when halo came out, it wasnt really "second only to HL1". deus ex, system shock,thief were still way better

Halo is a very complete package. It has single-player, co-op (online and local), online and local multiplayer modes, vehicles, great AI, a very colourful art style, as good controls as your going to get with a traditional analogue controller, Forge, player statistics. It really does a good job of being all things to all people. Im not saying you have to like it, but it is a great package. The only thing its missing is bots. Wish more FPS's games had bots.

There's life in the old horse yet. Bioshocks art-deco art style coupled with its atmosphere was classic. Game like System shock 2 and Deus ex combine choice, multiple play styles and RPG's elements to create a very innovative, unique experience.

I wouldn't discount FPS's. Its just a very popular oversaturated genre. Most of its crap but there are lots of really good games if you look hard enough.

So to answer your question. You add something new, whether that be elements from another genre to a new art direction, to philosophical elemets, etc etc whatever you want.  FPS as a genre has seen more innovation then most other genre's. Physics and gravity puzzles were done in FPS's long before Mario galaxy was released for example.

how not to make a a non generic FPS?

Step 1: put master chief in your game and call it halo
Step 2: market the game like it's the second comming of Jesus Christ
Step 3: be an American developer making the game exclusively for an American console and target the American trigger happy crowd
Step 4: inject enough money into the game to feed a small country

and vuala instant non generic FPS which sells like crazy

Very funny.. Except for step 1 you could say the same about CoD4. But you don't see people bashing it, simply because it's not tied to MS.