I second the recommendation for Red Dead Redemption. Fantastic game.
Though I have to disagree on L.A. Noire. Love that game. Insanely detailed recreation of 1947 Los Angeles. The attention to detail is insane and the size of the map is very impressive. And pile on top of that classic film noir storytelling and baby, you got a stew goin'.