Call of Juarez, both of them are pretty great examples of how cool a Western can be. The storyline is pure gold if you like Clint Eastwood movies, but what I liked is how the second game is actually a prequel. In the first game you play the older brother who's a preacher, you can actually equip a bible and say a little prayer before shooting someone in the groin. The second game starts with the civil war, but the plot links between the games are really cool. I tend to only even notice the plot if it's really good, but the games are really excellent, I enjoyed them both a lot more than most games.
Red Dead Redemption will be out in a few weeks, that'll be the Western game to have, start a posse, proper open world gameplay, it'll go on for years. I can seriously see Red Dead being as big as GTA4, it might even have more longevity as theres some really cool multiplayer modes. I'm looking forward to that, if you haven't already, go check it on YouTube.
Really I think that with modern PC's and consoles, those 3 games are the only real options for Westerns, good options - but it's a genre that tends to be neglected for a decade then creeps back, maybe after a designer has a Clint Eastwood marathon

.