"Don't be a fool Marshall"
Outlaws is one of my favourites. The gameplay was fairly simple, and felt dated even at the time, but there was lots of fun to be had, and the soundtrack and story were great.
I enjoyed Red Dead Redemption a lot, but it wasn't perfect by any means. I thought the biggest thing was that you had a lot of freedom in the open-world bits (how you behaved affected how people treated you, etc.), but none of that really counted for anything in the main story, which was absolutely set.
The absolute worst western game I ever played (probably the worst game I ever played) was Wanted Guns ( http://www.mobygames.com/game/wanted-dead-or-alive ). I think they'd decided it was too easy, and made it harder by turning the sensitivity of the mouse right down, so it took about 30 seconds to aim at anything on the other side of the screen.