I'm interpreting your question to mean games with a wide variety of different paths, and few save-or-die guess correctly to continue choices.
(Disclaimer: I'm only suggesting games I've played, and there's a lot I haven't.)
Story-based choice-heavy games:
The book of vanishing tales- By Camelon. The plot here is the same (traveling to the city), but you can take a different path each time. Each choice strongly affects what ending you reach, and there are 10+ different endings.
Endmaster's early games- Repression, A very special choose your story, Tales from the basement, TRASH, Geek, Alpha wolf, Imagination, etc. Endmaster's later games are excellent, but less choice-heavy, having plot-based choices occur only at critical moments. Paradise violated I especially recommend, in my mind it's the game on the site that best balances the choice-narrative trade off. Each of these are cave-of-time style with various endings.
Gower's games- All of Gower's games have a variety of endings, and a LOT of different paths that can be taken to get to them. Private game for Natalie and Sabbatical Report probably best fit your request.
Uneasy Lies the Head- Another one by Camelon. Nice branching, lots of endings, lots of variety.
Hastings, 1066- Great game, LOTS of branching, good flavor choices. I've only explored a few of the paths.
Price of Freedom- A linear game, but including a lot of different chioces for how the story proceeds, like you said in your question.
Game-based choice-heavy games:
These stories include game-like elements, such as stats and items. Most are open-map games, allowing for a LOT of exploration and different playthroughs.
Dead man walking- Open map zombie survival game, with a near infinite amount of possible playthroughs. By Berka Zerka.
Dungeon Stompage- Also by Berka Zerka. Open map dungeon exploration game with a tight and satisfying plot, with 10+ possible endings.
Will's Detective games- Open map exploration games involving solving a mystery based on collecting clues. I hear Will's other games are also good in this respect.
Secrets of the Crag- Shamelss self-plug. An open map stats-based dungeon exploration game with 50+ locations and multiple activities at each location. 10+ endings unlocked based on your choices in the game.
Hope this is what you were looking for!
