"Red Dead Redemption" is a game best described as "GTA in the Old West". More than a normal sandbox game, Red Dead Redemption uses a lot of specific features and stylistic choices from the GTA series. In this way, it shares many of the series' shortcomings, but also improves on the openness and freedom of the sandbox concept.
"Red Dead Redemption" takes place in the early 1900s, in the last days of the Wild West. The player character is John Marston, a former outlaw now being coerced into hunting his former gang-mates. The game tries to convey a sense of rural desolation - there's a lot of empty space between towns populated by wild animals and the occasional rider or messenger. The environment is sort of a mish-mash of Western stereotypes, including Southwestern deserts, boomtowns, old mines, and jaunts over the border to Mexico.
Like most GTA games, "Red Dead Redemption" can best be described as an open-world environment with a linear set of missions. In short, you can tool around all you want in the open world segments, but eventually you're going to have to do the missions to move the story along and access new areas. However, unlike GTA (where all you could really do in the open world was mess around), the open world of RDR is a lot more developed and natural. For example, while GTA was a busy city with very few actual events, RDR focuses a lot more on random roadside events - horse thieves, stagecoach robberies, and bandit ambushes. How you participate in these events (by helping the innocent, helping the robbers, or ignoring it entirely) affects your honor rating, the game's version of a standard morality meter.
The game has a lot to do besides fighting criminals (or being one). Towns and settlements will inevitably have some games of chance like Poker, Blackjack, or Horseshoes, and you can while away the hours making or losing money. Out in the wilderness, you can hunt and skin animals, then sell their meat and pelts in town for extra cash. Still, the game feels largely objective-oriented. You can buy houses, but only to save in or change outfits in. You can become famous and well-known, but only by doing missions or random events. It feels largely like a world that you can only interact with in the context of furthering your main story goals.
The gameplay itself is good. Gunplay is fast and lethal; the player character has regenerating health, but not that much health in total. This means that if you survive an initial few shots and get to cover, you'll probably be okay, but you can't run through hails of bullets or anything. In combat terms, the game's main "equalizer" is the Dead-Eye mode. This is a mode that slows down time and, later, allows you to target your shots for a consecutive burst of gunfire. It's neat in theory, but eventually becomes a crutch. You get so much "juice" for Dead-Eye mode that it's easier to start and finish every fight in a single use of it than to actually try and fight all the enemies before you. The guns are interesting, but hardly unique. It's the usual layout of pistols, rifles, shotguns, and so on, except that it's Wild West technology instead of modern technology.
The game has a multiplayer mode that seems interesting on paper, but isn't that great in actual practice. Essentially, it's a scaled-down MMO version of the main game. Players have access to the whole map, and can join up in posses with other players to hunt outlaws or rob stagecoaches. However, the lack of real interaction rears its ugly head again, because there's only so much you can actually do in the world. The more conventional deathmatch modes are sort of fun, but hardly groundbreaking.
Overall, Red Dead Redemption is a reasonably fun game. Still, the forced mission segments were more annoying than fun (especially in plot terms - "hey, these guys are clearly evil, maybe we should stop working with them before they betray us"). The sandbox makes up for it in a lot of ways, but even that is too limited to be great. However, as Wild West games go, you could do a lot worse.