Mass Effect 2. It actually had real writers working on it! How innovative! Plus, the gameplay actually was as good as it's competitors in the TPS market, and the few complaints I've got about the game (stupid mining) are easily overlooked in the face of such a good story.
Second up, I'd pick Metro 2033. It's like Half-life 2, only with a more interesting story, better graphics, better gunplay, and AI that actually does stuff other than standing around (even if it is kind of stupid). No gravity gun, but with gameplay that wasn't inspired purely by Doom, I'll live with it.