I think the question doesn’t exactly have to be “How much choice?” but rather “What choices are the most compelling?” I have studied a ridiculous amount of theory on interactivity, and this is what I’ve found in the realm of choices: people generally fall into 3 categories when playing games.
CATEGORY ONE: Competency. People like to feel like they can do things well. This, obviously, translates to choices that rely on player stats or prior decisions. Can your hero stop the villain? You better hope you allocated your skills properly! To translate this into a choice would be easy. Is your character sneaking into the library after school? Put in a choice asking if they sneak in through a window, convince a guard to let them in, or if they pick the locked door. Even if your game doesn’t have skills, you can put a puzzle in, which involves finding a key or some such thing.
CATEGORY TWO: Autonomy. Some people like to feel in control of their own fate. Obviously, ALL choices can trigger this, but it is especially vital to have choices that clearly change things. If I have the option to save the princess instead of defending my soldiers, I want there to be a scene later on where the princess matters, and the same in reverse. These are the kinds of choices most people here tout as the most important, and that’s understandable. They can be BIG branching choices like “Should Geralt help the humans or the elves?” that take you to completely different places, or they can be subtler things, like whether to save Carly or Doug, that ultimately don’t change the plot’s trajectory, but do change the actors in it.
CATEGORY THREE: Sociability. Some folks like to feel connected to the games they’re playing. These are the people who play for the romances, or choose a personality and stick with it because they feel they can relate to the characters action. In more traditional games, these are also the folks who are playing multiplayer. To add these choices in is simple. Give the player a chance every so often to react to something with emotion without having to worry about stats or repercussions. You can also give them the option to flirt or build friendships/rivalries with other characters. These are, in my opinion, the most effective choices at drawing people into the game, as I know more people who say things like “I want to see if Heather ever gets out of her shell!” than “Will we ever solve this zombie problem?” People remember people.
OKAY so I talked too much, but hopefully my point is made! Having huge amounts of choices doesn’t always equal good choices, and having every branch is cumbersome not only to the writer, but the player as well. Telltale’s stuff, as you mentioned, does a good job of 2 and 3, with the “puzzles” you have to solve taking the place of 1. Mass Effect thrives on all three. Shooting for 1, Big decisions for 2, Conversation for 3. I’LL WRAP THIS UP: Replay value can be determined by more than just the endings/branches. If you focus on having realistic conversation, for example, even a linear plot can feel like a new experience when such and such who was your friend last time hates you this time. Even things like Borderlands, which have no true branches at all, have me replaying them just to hear the alternate dialogue for a different character class. You just have to make the choices you do include STRONG.
Yikes, I talk too much!