Red Dead Redemption
The grand irony of Red Dead Redemption is that, while its Wild West is leagues less busy and populated than Liberty City, it has significantly more meaningful side-missions and naturally emergent gameplay. Personally I miss the cars and highways -- but Redemption does a good job of keeping things entertaining, aside from some menial ranch work (which I guess is John Marston's equivalent of going bowling or playing pool). And of course, the storytelling is excellent, even if the "reforming outlaw with a grudge to settle" premise is a little familiar.
Progress: Tracking outlaws in New Austin