Batman: Arkham Assylum and Arkham City
Burnout Paradise
Dragon Age series
Dark Souls + Demon's Souls
Battlefield 3 if you trust the hype.
Borderlands (A sequel is coming up if you want to wait for that)
Splinter Cell series
Ninja Gaiden 2
Grand Theft Auto 4
Assassin's Creed Series (If you care about the story, go it in order. Otherwise, start with the second game or wait for the third to come out soon)
Asura's Wrath (Suggested Rental than purchase)
Bioshock series (I prefer the first to the second, a new title releases this year)
Brutal Legend (Stars Jack Black, what's not to love?)
Bully (A Rockstar Title that got a judge to publically denounce Jack Thompson's opinion. Yay!)
Dead Rising Series (You'll prefer the story in 1 but the freedom in 2, DLC and Case West to avoid unless you care for story sake)
Fable Series (My favorite is 2, but the whole series is pretty linear despite the areas you can go)
Fallout Series + DLC (DLC adds story, play time and more. Start with Fallout 3 for story + simplicity or New Vegas if you want to focus where the first two games existed + all enemies free to fight from the beginning, even when one hit deaths occur)
Gears of War Series (I've heard that 1 is better than 2 but I've only played the second)
Halo Series
Hitman Series
LA Noire
Mass Effect Series (If you don't mind DLC for game 3's ending)
Overlord Series (Suggested Rental)
Prey (Suggested Rental, new title recently cancelled I believe)
Prototype (Suggested Rental, sequel currently released)
Saints Row Series
The Darkness Series
The Elder Scrolls Series
Bayonetta
X-Men Origins: Wolverine (Suggested Rental)
There's some decent titles on XBL as well, though I've only purchased and played Scott Pilgrim Vs The World. Most downloadable games offer a demo.