No one's started a topic on this yet, right?
The Marathon Trilogy, mostly-developed and published by Bungie (Double Aught handled Marathon Infinity, the third game) from late '94 to '96, is the spiritual predecessor to Halo (in fact, the two series were directly connected in an early draft)--story-heavy FPSes with many layers of depth and a great deal of mind-screwy ambiguity in the vein of William Gibson, at a time when most FPSes could be summed up as "it moves, it dies". Marathon introduced a number of other innovations to the genre, like mouselook (and the ability to aim vertically) and grenade-hopping.
A very, very short summary: you're a Security Officer on the UESC
Marathon who is at first impeded by, then ends up working for a Rampant AI, Durandal. Neither of you are as you seem, whether in terms of motivations or nature. You're also not the dude(s) in the second link.
All three games, along with some notable fan scenarios, can be played on modern OSes via
Aleph One. If you've got a Mac capable of handling Classic software and wanna go old-school, you can grab the .SITs
here (the Trilogy was largely Mac-exclusive). If you just want to read the terminals (which are the primary method of story conveyance), the
Story Page has them all, along with two decades' worth of analysis and speculation (protip: write your own notes first).