In my mind, the difference between objective-based first person shooters and the more traditional key/button collect/push type is a matter of linearity (is that a word?).
Doom, Quake, Unreal, Half-Life, and Halo all followed this formula. Games where certain objectives must be fulfilled before you can progress.
Games like Goldeneye are open in design, allowing you to complete the objectives in a flexible order. A lot of 'realistic' first person shooters (war, modern and historical military games) use this pattern. Games like Dark Forces, Stryfe and System Shock are the early innovators here.
To be honest, I prefer the more combat oriented first person shooters. Halo, for example, is totally old-school in its design and execution. Doom 3 never deviated further than 'find objective item and proceed through previously locked door'. Half-Life was also totally linear - one scripted event triggers the opening of your next path.
I'm interested to see how Half-Life 2 and Halo 2 further their respective series'.