King's Quest 6 fits the bill for me. I love that there's not really some dialogue choice that puts you down a different path, but just basic game choices make things play out in different ways.
Even if it doesn't change the overall story, I love it when there are multiple solutions to puzzles. It's at least altering how the story plays out and makes it more tailored to the person playing it. Even crap like the two ways to handle Orat and the start of the Deltaur in the first Space Quest has always been fascinating to me.
Honorable mention to how the RPG mechanics in Quest For Glory and Heroine's Quest alter how those stories play out.
Might not be what you were looking for. As someone who doesn't rank stories that high as being important to her adventure gaming, I did my best.