Red Dead Redemption is not the first of the so-called "sandbox games," games which spread a seemingly open world before the player and set very few boundaries on what the player can do, but it's one of the best, if not the best and it's definitely the first to come anywhere near to presenting a role playing experience. It doesn't achieve this by being more of a role playing game (by giving you the option to create the character or influence the narrative) it does it by being less of a sandbox game.
In Red Dead Redemption, you will not steal tanks and roll down city streets, launching rockets at passersby and hurling hookers off rooftops. For one thing, the game is set in the Old West, based on the Western United States in the historical period of the late 1800s and early 20th Century. There are no tanks or rocket launchers. You can hurl hookers off rooftops if you like, but you can't have sex with them - Marston is a married man and refuses their advances. The game put you into one of those rare historical eras during which modern society temporarily stretched beyond the boundaries of civilization, during which men and women inhabited a world for which they weren't entirely equipped. The result: all of the conveniences of civilized society with hardly any of the limitations on personal freedom, an environment seemingly custom-made for a sandbox game.
Yet due to this unique historical specificity, Red Dead Redemption limits your available actions to what could realistically be accomplished using the tools and techniques available at the time. There are cars, but John Marston doesn't know how to drive them, so you can't steal them. You can steal horses - even kill them - but you can't hurl them off a mountain because the horse just won't go there. The lawlessness of the Old West setting presents an opportunity for you to realistically indulge your most outlandish whims, but the strict historical setting enforces a harsh limitation on player agency which, instead of inhibiting the experience, actually serves to lift it above the norm.
Compare Red Dead Redemption to the genre-defining Grand Theft Auto series. The latest installment, Grand Theft Auto IV, has a similarly deep narrative to Red Dead Redemption, about a similarly conflicted outlaw attempting to effect a similar rehabilitation of his similarly dark past. Niko Bellic is an Eastern European import to the United States trying to get by in New York City. It's entirely possible to play that game, as Niko, doing the things Niko might do and experience a rich narrative as you shoot, drive and hooker-punch your way through his narrative arc, but the second you step out of that narrative path, the illusion becomes untenable.
It is entirely possible that Niko Bellic, the character, might be enough of a social degenerate to willingly act in the many untoward ways Grand Theft Auto IV allows you to force him to act, but it's unreasonable to believe that the environment of New York City (or any reasonably believable facsimile), would react to Niko in the way Grand Theft Auto IV's Liberty City is programmed to react. Anyone stealing an actual tank in an actual New York City would very quickly wind up in an actual jail or an actual morgue. Throw a few handfuls of hookers off a rooftop, or spray the city with as many bullets as Niko does, even in the narrative missions, and there would be no end to the manhunt for him - even if he spray-painted his car.