Since jumping back in and playing Duke again recently, I've noticed it's a lot less linear than a lot of modern FPS.
Modern FPS: (I'm using HL2 as a basis, since I just finished it and it's fresh in my mind) Gameplay is linear, though not a straight line. Sometimes the path is not obvious and you have to look for it, which sort of makes you feel like you're not having your hand held. Occasionally the path will split, but 90% of the time one of the paths will be a dead end with some items/powerups. (leading to the small frustration of realizing you took the real path, but you'd rather have takent he dead end first, for the powerups.)
Duke3D: In the first level, you can go through the side entrance of the theater, or the locked up front entrance (if you know where to get the rocket launcher). When you get to the lobby, you can go to the bathroom, up to the arcade, or up to the projection room, and they all connect with secret passages or air ducts. Then when you grab the jetpack it opens up a bit more of the level, and when you go back to areas you've cleared, there's more enemies a lot of times. The whole damn map feels like a big playground. It's like a lot of the maps were designed with deathmatch in mind, and they feel like playgrounds to explore while blowing away aliens. I'd almost go as far as saying it's got the feel of a sandbox game, but on a very small scale. Enemies are in specific places, and then you can come at them from wherever.
Side rant: anyone else feel like shooters that give you a squad feel even more linear? They're telling you exactly where to go, and you've got guys yelling at you to get there, so you don't get to explore. (I'm thinking back at early levels (the only parts I've played, big surprise) of CoD4. At least in Half-Life 2 you're plot-important AI teammates are invincible, and the rest are expendable and on auto-follow.