Maybe I'm just boring, but I find symmetrical map design (in multiplayer) to be the most fun. Both sides have exactly the same resources, and all the really powerful goodies in the middle draw the players out of their bases to fight. The original Halo was especially good at this I feel; any map can be played in any mode and it's pretty fair, as long as nobody gets a banshee or a tank in a free-for-all game type. The bases still have some advantages/disadvantages (I think it was Blue base in Blood Gulch that had the fuel rod gun, while Red Base had that shady sniper position looking over it), but they're symmetrical enough that it's even.
A to B waypoint objectives
If you took the objectives out of Halo 2 and just pointed the player towards the end of the level, it'd essentially be the same game in every respect. You aren't actually accomplishing anything by completing an objective in that game; you're just moving from A to B. I don't think this is a problem with linear map design (some of Doom's maps are fucking ridiculous and could stand to be trimmed down IMO), but with player interaction. In Halo, completing an objective usually means going somewhere and maybe pressing a button, but nothing more than that.
In Goldeneye or Perfect Dark, objectives are a lot more complicated. In the second mission of Goldeneye, you have to blow up a bunch of chemical tanks and escape the facility. Instead of pressing a button and watching a cutscene, you have to actually blow up the tanks with explosives and run away from soldiers to get out of the level. In one level of Perfect Dark, you have to create a distraction so that you can sneak into a building; to complete this objective, you have to reprogram an automated taxi so that it crashes into a security robot. Already, there's two pre-2000 games with gameplay more complicated than the most technologically advanced shooters of our era.