- Non-linear level design. Refer here :
http://cdn.duelinganalogs.com/wp-content/uploads/2010/11/fps-map-design.png - Difficulty levels. Some people are pansies. Some can handle challenge.
- Running all the god-damned time. No sprinting. I want to run like an electrocuted cat across velcro.
- Episode Level-based design. Short 30-60 minute levels, broken up into episodes, each with about 10 levels.
- Save anywhere. No stupid checkpoints.
- Actual secrets. None of this "run to the back of a pillar, and voila! Secret!" (looking at you Painkiller)
- Having it be moddable with a level-editor would go a long way towards extending its life.
- Health packs. Regen health sucks.
- Armor. Reduces health by a given percentage depending on type.
- Prefer billboarded sprites over low-poly models. Not to say I don't play some older 3D games, just that they tend to not hold up quite as well as hand-drawn sprite-based games. Doom & Duke 3D > Quake.
Keycards I wouldn't mind. A good compromise with them is to have lower difficulty levels not require them, or to have a non-traditional difficulty system, when the player can select a series of options they want on or off, including that, additional health for enemies, reduced damage for player weapons, more obvious secrets. Then let the player select the options on game start (and save them in a setting file! So the player can have a default and get right into the action)