I distilled the qualities of a FPS down to seven things to consider:
1. Movement is variable and interesting. Put jetpacks, portal guns, double jumps, zero-G, teleportation, burst movement, ect. into your games!
2. Weapons, tools, vehicles and defences are balanced. I cite Tribes 2 as an excellent example of this. If you have one type of weapon (like a grenade launcher) don't make a dozen iterations of it but instead one grenade launcher that can preset to behave in a different way or have a cooldown on certain abilities. Give the players the power - but in ways that does not make every player a superman.
2. Weapons and tools that can be combined or together to produce different results and therefore generate interesting gameplay. Allow players to enjoy the feeling of combining weapons and/or tools together to create an interesting tactic no one thought of and executing it with success. The first "rocket jumping" is a prime example.
3. Environments that vary and require forethought to navigate. No one likes playing over and over in a hallway ... nuff said!
4. In single player mode, AI that is not only good at predictive shooting but use tactics with an element of self preservation.
5. In multiplayer mode, make the players earn their victories. Victories without skill or effort produce a game that will be soon forgotten.
6. Introduce elements that make a gamer say "wow" longer than the first 5 minutes. Beautiful graphics are nice to have in a game but if it at the expense of a game with interesting and rewarding gameplay, then it is just a marketing tool to sell a substandard game.
7. Give the player(s) more freedom to create their own modifications, skins, models and maps. In these modded servers, make sure people know they are modded and not the original game. Giving the player(s) more freedom makes your game more awesome and fun. I cite Minecraft, Gary's mod and Unreal as prime examples of this.