Red Dead Redemption was something new and special. It galloped up out of nowhere - I hadn't seen any hype for this game at all - and it slung a lasso around my heart. It's an interesting juxtaposition - the Wild West is an area that hasn't been frequently covered in games, whereas sandboxes have been done to death and back again. And it worked. Given that it was made by Rockstar, a lot of GTA IV went into RDR, but in every way GTA IV got it wrong, Red Dead Redemption got it right.
The soundtrack was beautiful, the graphics and the environment doubly so, and the gameplay was intuitive and fun. The only downside I can see was that the story sagged a little bit around the middle, which is a shame because the first and last acts had great writing. The character of John Marston as a tragic hero will be one of the stories from this generation that will stay with me.
While the single player was fantastic, the online really kicked it into another level from good game to daily social activity with friends. Possess free roaming the plains hunting bandits, buffalo and you if you weren't careful. Fun and intense co-op missions. Silly gambling games like Liar's Dice and poker. Horse races. Oh, the horse races. Pegging Iceglow from 100 feet with a hunting knife, or the time myself and DK encountered a glitch where 40+ wild boar spawned and kept tramping us to death, with boar coming back from the dead to nail us.
Oh, and there was zombie DLC where you could ride a unicorn. So there's that.