If you want a game with a plot that can change drastically depending on the choices you make then allow me to recommend The Age of Decadence.
In my first game I played an archeologist with zero combat skills but a huge focus on all kinds of social abilities. This allowed me to see a lot of the intrigue going on between various guilds and political groups as I became involved as a form of diplomat/agent. Never once did my character get involved in any combat.
In another game I went in as a full combat specialist and because of this my character never saw any of the shady backroom deals that the other character had seen. Instead it was a much more straight-forward story about following orders and killing those that needed killing.
And that's before getting to all the different endings and the various requirements for them!
There are a few examples in RTS and wargame series where something like this applies, though the amount of choice you have at a particular point is limited. Some have campaigns where failure on a particular mission puts you down a different path, or options to support or oppose one faction. An old and obscure example would be one of the games in the Great Battles Of... series (I think Great Battles of Hannibal) where failing to win certain engagements meant fighting a different series of battles and depending on your performance in those could lead to winning in a different way. Dawn of War 1 had some of that too., as did Cossacks in some scenarios.
Of course there are plenty of games with no set plot - from Mount and Blade to Civilization and Stellaris - but I don't think they're a good example of branching plot. After all, there's no plot to branch.
Never played either of them, but I was under the impression that both Shadow the Hedgehog and at least the first Ogre Battle game had largely branching storylines and a lot of possible endings depending on the choices made during the game.
It's interesting how many of these responses have come up with strategy games as examples. I wonder if there's a specific reason for that; is it that it's a genre where an unusually high percentage of the total work goes into polishing the game's core systems, and creating "extra" content that many players might not see is relatively less time-intensive by comparison? Or is it that they're designed under the assumption that a dedicated player will play through multiple times and experience most of the game's content, so it's not really seen as "extra" content in the first place? (I know the latter is the case with visual novels, which have also been brought as examples; the default expectation, at least in the Japanese market, is that if a player enjoys a VN, they'll want to see every route and every ending.)
Star Fox Command has a lot of branching from the very beginning. It's got visual novel-style story cutscenes, and most of them give you a choice which leads to different followup missions, and often changes the party composition.
You can end up with one of the party members quitting the Star Fox team and joining recurring villains Star Wolf instead, or have Falco break off to form his own squad. There are nine endings in total, but lots of paths you can use to play through the game.
Way of the Samurai 3 (and presumably the others in the series, though I haven't played them myself) has about twenty different endings, generally all quite different from each other, and the means of arriving at them is different in each case. You can basically side with any of the major NPCs in the game and follow their plot to the end, so the game can play out as a personal revenge story, quest for peace, embrace of tyranny in the name of order, greed for the sake of greed, and so on. There's even an ending for choosing not to engage with any of the potential plotlines.
It's a game that's designed from the ground up to consist of short playthroughs (you can get through a playthrough in under an hour without too much effort, if you pick one of the shorter plots and you know what you're doing) but with its replay value based on exploring the different plots.
This was the series I was coming here to post about myself.
Yes, the “Way of the Samurai” games are all like that. 3 and 4 are available on steam which is where I found them. I think this series really embraced the idea of a branching story. There is of course a “best” ending which can be next to impossible to get. The fourth in the series requires you go one scene without losing three mini-games, but you only get the second mini game if you beat the first. Ditto for beating the second to get the third.
It’s really good writing though I thought. I felt really moved by each outcome.