Mass Effect has the best Universe, to be honest.
Half-Life came in a close second, which sucked because HL1 was an amazing universe, and established things so well, but HL2 kind of just switched to a Physics demo, referencing the HL1 Game concepts rather than establishing the whole HL Universe again.
Halo *had* a universe, until all of the Power Armor that get their hardon to teabagging dead corpses came in and shifted Bungie's mindset to building a Universe to just building the Multiplayer. Halo 2's story was non-existent and showed that all they did was work in the MP. Halo 3's story was a repeat of everything else, and did the same.
Deus-Ex was nice, but, seriously, it just featured guns.
Starcraft was nice, and the new game is cool, but it loses points because Blizzard took 12 years to get the Sequel.
Metroid is nice, but it's overdone, like every other Nintendo game. Yahtzee has a good point that Nintendo is innovative in the gameplay mechanics (minus Galaxy 2), however, their writing and new character ideas department is given, what, 10$ a year? Come on, how come it takes them a DECADE for them to realize that "Duhhh, maybe a decade of not having new characters is a bad thing?"