Halo is way more flexible to me than goldeneye, although that's more because I like to try different weapon combos to get through the different levels, and in goldeneye there's just not nearly the kind of weapon variety, not to mention the same weapon limitations of Halo (I know it has tons of guns, but they feel more similar to me than most other FPS games do with their weapon selection). but both of them have moments where there's what can feel like just bland corridor shooting (although this plagues Halo a lot more than it does Goldeneye). As far as what makes Quake 2 so doom-like (which should be easy to see), it's both all of the things you bitched about (key/switch hunting, how much of this was doom, remember? and it's ironic to complain about going through boringly similar environments when that's one of the worst things about Halo) and some of the other things traditional with Doom (triggered events, big variety of weird/freakish enemies). The only thing missing is the tons of enemies at once from Doom, which is a big part of it, but it's still basically like having 50% of Doom's gameplay in Quake 2's singleplayer (which is more than pretty much any 3d fps except maybe Serious Sam has done to get close to Doom). It might just be me, but I enjoyed walking into some of the traps of the Doom games that you were forced to get through as much or more than killing hundreds of enemies, because there's really nothing new from said enemies when you get down to it. Regardless, I enjoyed Quake 2's singleplayer more than Goldeneye, because after the humor of shooting a guard in the groin wears off there's really not much else left that impresses me too much with the game. And it's not like I'm saying Quake 2 is a great game or anything, just that it and Goldeneye are both merely above-average in the grand scheme of FPS games.
And as scripted as Call of Duty is, it's still really fun to go along for the ride, and is great twitch fun on Veteran difficulty. I wouldn't call it the greatest FPS ever, either, but of all the recent FPS games only NOLF 2 (which is better than the first because it's got deeper gameplay, especially in the stealth aspects and with the skill system that rewards you in the same manner as the original does, but better - everything else is pretty much equal), HL2 and Halo 2 (from what I've played of the genre in the past 2 years, and I was pretty late getting to the NOLF series) are better than it. But that's for strictly FPS games (NOLF 2, while borrowing the deus ex skill system, really isn't hybridized much).