The King of Chicago
The King of Chicago is a 1987 interactive fiction game by Doug Sharp about a gangster trying to get control of Chicago after Capone is arrested. The scene selection system was particularly clever, making each playthrough different while taking into account player decisions.
Playing through The King of Chicago you're thrown right into the story, but the opening scene differs each time - sometimes the Old Man (your gang's current boss) is already dead, sometimes you're in the process of shooting him, and sometimes you haven't actually decided to kill him yet.
As you play through the story scenes transition like in a movie, and within a scene you choose dialog options from thought bubbles and characters respond intelligently. Some portions are more game like - there's a few action sequences where you throw bombs or shoot people and a few points where you can reorganize your finances - but most scenes are just narrative choices.
The game is pretty hard, and most of my playthroughs ended in the electric chair. Looking online it seems like the easiest way to win is to gamble everything early, hit the jackpot, and spend your way to victory. Still, even without winning, the variety in each playthrough never left me frustrated by the fact that I was "losing" or gave me the impression I was pointlessly playing the same stage over and over again.
The implemenation of the narrative engine is described in some detail in Doug Sharp's notes from his 1989 talk Story vs. Game: the smallest unit of scenes is an "episode", which might include a few cuts structured in a familiar visual-novel style with branching narrative. Episodes are then grouped into ordered "phases" within "sequences", where a sequence is like a subplot. It's not entirely clear from the description but I think episodes within a phase are assumed to be mutually exclusive; for example, in a sequence about assassinating someone, one phase might have episodes for attempts at their office and at their home (assuming you wouldn't do both). Sequences have further logical groupings for overall story flow (beginning and ending sequences) and variety in the midgame (different characters have different sequence groups so scenes alternate their focus).
Which scene plays at any given time is selected by a process called "Narraton". Narraton selects episodes, not sequences; sequences are used to enforce ordering but don't have conditions of their own. Narraton selects episodes by comparing certain global variables that range from 0 to 100 to per-episode requirements using a least-squares fit; Doug's talk goes in to more detail on this, but basically it means that scenes are loosely coupled, preserving logical connections without ever using explicit linking. At its best this made adding content easy:
A big advantage of using an episode selector rather than a more explicit type of branching was that it let me improvise more freely. If I got a great idea for a new episode, I could set it up in its own sequence, assign it keys and trust that it would be selected appropriately. I could also come up with a new alternative plot twist for a sequence, write it and throw it in without rewriting any of the others episodes in the sequence.