I liked Bioshock 2. Better gameplay, better ending, and it criticizes the opposite philosophical viewpoint of the first game's.
The Mass Effect series is a must. In my opinion, Mass Effect 2 is the best game ever made.
Fallout 3/NV if you like big RPGs (there's also the elder scrolls games like Skyrim if you're into the peasantry/fantasy stuff).
Left 4 Dead 2 if you like zombies (as if anyone doesn't).
Mirror's Edge is really fun, but the fighting near the end can be frustrating.
If you like horror (specifically Sci-Fi Horror), the Dead Space series is the absolute best in terms of gameplay (and the atmosphere is great too).
Alan Wake is another horror game with great gameplay (and great storytelling too).
Deus Ex: Human Revolution is another good game if you like Sci-Fi.
And get Portal 2 after you finish Portal (which takes about 2 hours).
XBLA Must-Haves:
Castle Crashers
Beyond Good & Evil HD
