Given the popularity of the genre in American film and folklore, it's really quite bizarre that we see so few Western-themed videogames. Granted, I can't think of any off the top of my head that have been especially successful, but it's hard to say if that's because gamers are for some reason particularly uninterested in the Western milieu or because they make so few of them in the first place. Neversoft's Gun is a notable exception, squeezing most of the standard Western motifs into the free-roaming adventure mold established and popularized by Grand Theft Auto. The pacing, however, is a bit different; in GTA games, while the story missions do generally follow each other chronologically, there isn't a great sense of urgency connecting them, and it doesn't interfere with the experience to wander around and explore the world for a while.
Gun spins a fairly tight tale, and one that doesn't especially lend itself to taking breaks. The narrative proceeds with a sense of urgency that the rule system doesn't bear out--there really is no penalty if you decide to wander around doing odd jobs and mining for gold while a friend of yours is being held and tortured by the bad guys. I enjoy the side missions a great deal, and tend to do them as soon as they become available; this play style tends to make the story a bit disjointed.
This might not, in fact, be an accident. The gameplay structure of Gun is cyclical: story missions open up side missions and new weapons. Side missions boost character stats and allow the player to earn money. Money is spent on upgrades. So playing straight through the story missions consecutively allows no time for stat growth or upgrades. I assume this would make the game unbearably hard, and there are key points in which the game actually reminds you that things are going to get harder soon, and you'd better raise your stats. These key points generally arrive at less time-sensitive moments than the "kidnapped comrade" scenario I mentioned above, and it's possible that this is how the designers intended/expected players to progress: hours of concentrated play on story missions followed by hours of concentrated play on side missions. At any rate, in practice the gameplay structure allows players to change the difficulty of the game to an unusual degree.
In addition to screwing with the dramatic tension of the story, doing all the side missions as soon as they come makes the game, well, pretty damn easy. By the second half of the game, your character is practically bulletproof, and most of the bad guys go down if you look at them funny. You're not just heroic, you're bloody invincible.
Which might be the point. Someone who prioritizes the ludus game exclusively would find a brutal, dramatic game with a harsh difficulty curve emphasizing the usual FPS bag of tricks, such traps, ranging, proper weapon selection, stealth kills, etc. Not exactly a realistic story--the Western is not especially well-known for "realistic"--but not out of step with, say, modern film narratives. Conversely, someone who goes off the path into paidia as much as possible ends up with something more closely resembling a tall tale: not only does the hero beat the bad guys, he does so without a great deal of difficulty; he gets shot hundreds of times and lives to tell the tale; he hunts better with a bow and arrow than the best Indian hunter; he does the jobs the sheriff and federal marshall couldn't; he's the best horseman in the Pony Express, the best gambler, the best prospector. It's common enough for the sheer hyperbolic weight of the protagonist's heroic accomplishments to swamp the main storyline in a game, but in a milieu that's always half-folktale anyway, it seems strangely appropriate. Accident or not, the tension between ludus and paidia exerts its own pull on the game narrative, resulting in a storyline that's as pleasantly flexible as those concerning any of our "real" Western demigods.