More generally are you thinking about singleplayer or multiplayer? Melee or ranged FPS?
(Singleplayer) The original Red Faction levels toyed with the idea of linear progression. There would be branches in the pathway that then lead to dead ends a bit later, but you wouldn't realise this. Instead you would get caught in a loop (like a circle drawn at the end of a terminating line), convinced that you must be missing some doorway off the to the side somewhere. After checking a walkthrough you would find you need to backtrack quite a way and eg jump into a ventilation fan to get back on a path that isn't a dead end.
(Multiplayer) Tremulous/Unvaquished had some interesting level design problems because of it asymmetric teams (aliens: mostly melee, humans: ranged). Big open spaces vs tight corridors favoured one over the other, and it got a lot more complex with the first-person base building mechanics (which interacted in weird an interesting ways with level geometry, esp to form traps with turrets).
(Multiplayer) Most modern online first-person shooters give heavy advantage to a person walking around a corner or doorway, due to the inherent problems of ping and player prediction. Interestingly some gameplay mechanics (eg accuracy of weapons depending on movement speed) can help counteract this. This is what makes corners in games like Counterstrike so "random" feeling, there is a big advantage given to both the walker and the camper watching the corner, so the outcome is very unstable.
Specific level of interest in Tremulous (asymmetric aliens vs humans): ATCS. The small base area with its complex mini-walls and two levels allowed for interesting base building layouts. You could hide the giant, main central reactor somewhere clever in there but a jumping alien would then be able to get on top and damage it whilst hiding from your turrets. Big, heavy aliens would have to rush through defences on the floor but nimbler ones could crawl the walls or jump up to the second floor, interacting with defences in interesting ways.
The centre room of the map (a big outside building with a ramp to the roof and walkway around both sides) allowed some verticality, but only when the humans and aliens evolved their jetpacks and jumping forms later on. Entirely new gameplay strats would appear as things progressed, eg to trap or ambush humans from above.
The second path of the map was a kinked tunnel between the bases. It was a very different kind of combat, not as much fun but it served its purpose as something to prevent one strategy dominating the map.
Specific level of interest