The example of Red Dead Redemption is interesting in that, if one did want to replay it, there'd be a lot of meat there to make a replay interesting. Alternate ways of fighting enemies, finishing missions, hunting animals, and the order to perform missions in.
The trick I think, is that when it comes to longer games, what "replay value" actually means is that the game has rich content. It's not simply a scripted "monkey push button" corridor that makes a show of entertaining the player. You don't HAVE to ever replay a "replayable game" to greatly enjoy the benefits of it having that kind of content. Your first and only playthrough will feel richer because you know there's depth to it and the agency of the player actually makes a difference.
We really do have to bear in mind the different kinds of games too, with this subject. We still replay classic games, such as a 16-bit platformer, because those are essentially "arcade" games by today's standards. As such the enjoyment is in the activity itself, not just seeing the end credits or "finishing the story".
A good example of a rich "replayable" game genre today is the 3rd person brawler / action fighting game. Devil May Cry, Ninja Gaiden, etc. These games have long, meaty campaigns that would satisfy a person on one pass. They offer many difficulties and rewards for playing them again though. People who want that can benefit from it. People who don't still get to enjoy playing through a game that has rich mechanics and content. Enough that one could play through it again and feel refreshed.
I think some of the most disappointing, dull games I've played in the last generation or two have been games where the designers went into it aiming only to make a disposable, one-shot experience. IMHO that's a bad mentality. It encourages laziness in most kinds of games. You end up with a Heavy Rain - a game where the vaunted choices don't matter because there's only one real ending, one true killer, etc.
Edit:
Wanted to add that comparing games to movies, by saying "well, movies don't change when you watch them again, so games don't need replay value" is misinterpreting what the rich content of a good film is. A good film, one you want to watch over and over, has meat on its bones. There's something to enjoy, consider, analyze, think about, each time you see it. Good movies do have "replay value".
Think about it. How many films would you never care about seeing again? In fact, are turned off by the thought of watching again? Why's that? I'd bet odds are, that those films are a shallow, hollow experience.