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.
