On the PS2 I can think of Gun, Red Dead Revolver, Darkwatch and the Wild Arms games.
Gun is by all means what Red Dead Redemption wanted to be on the PS3 - a Western GTA - but only succeeds halfway. The story is actually interesting and there's a fucking awesome voice cast behind it (Thomas Jane, Lance Henriksen, Brad Dourif, Kris Kristofferson and Ron Perlman). The gameplay is fun as hell but for a sandbox the scope of the world and range of activities is a little disappointing. There're only a few things to do past the main campaign, which isn't particularly long, there're only two towns - starter town and a slightly larger one - and like I said not a whole lot to do in the meantime. If I recall correctly you even get locked out of those fun poker games once you actually beat them, which seems pointless.
Red Dead Revolver is RDR's PS2 ancestor but the story's completely unrelated and it's not actually a sandbox, just a pretty linear third person shooter. It's fun and quite challenging, actually. It's certainly more difficult than RDR. And there's a more cartoony vibe to it. Some of the characters you come by are straight out of the Borderlands school of quirky.
Darkwatch is a vampires-in-the-wild-west FPS. I don't have much to say about it. There's a silly moral system where you make choices along the way that add up to good guy skills or bad guy skills and ultimately determine the ending. And you can only carry 2 guns on you, which I know bums some people but was fine by me. My only real complaint would be how easy it is to simply rifle-butt your way through the enemies. Most common enemies go down with a single rifle-but so about 50% of the game feels like a First Person Puncher.
Wild Arms is a JRPG series I haven't actually played but the Western theme is prevalent in at least the first 3 or 4 games.