In my Cardinal Kingdom development, I explored the nature of choices in this sense. I didn't have anything as monumental to whether or not you'd fight a boss or not, but some choices made would pit you against people more often, creating "mini-bosses" in a way.
I didn't think the game should have a Fable state of being, but I wanted Link (and Zelda) to be recognized as either MORE or LESS of a hero, using a Hero Meter to determine this. The more people you help out, the easier the game becomes as you accumulate more allies and rights of passage, but the less people you help out allots you far fewer allies and you aren't known for good deeds which makes the game more difficult.
For instance, certain side quests to obtain items grant easy passage to (in this example) scaling a mountain. But not helping doesn't mean you can't reach the point on the mountain, it means the player has to find an alternative path. Also, as my design features the ability to kill "pedestrians" the view of Link (and Zelda) in the public eye changes from heroes who are less bothered by NPCs or heroes who are feared and therefore threatened more so by NPCs. Still, none of this affects the course of the game because of the level at which these side quests could possibly affect the outcome- essentially, in order to not have a thousand variations of the game the in-game adjustments would be minimal- would be too great. Instead, there would be points in the game where these allies are "critical."
Just one more example to cover the range of side quests. There is a rebel group who often comes to your aid throughout the game. It's a small band of NPCs, but depending on how many people you help, the rebels numbers can grow, allowing those moments where they are needed to be easier to get through. Ie. there are 3 Kokiri brothers who are abandoned and need food to survive so teaching them how to fish provides them this ability to do so and they become strong enough to join in these fights; there's a drought for Hyrule farmers and continuing down this sidequest provides ample food for the citizens, which would imply a stronger Hylian army and surrounding citizens, making them more capable of performing certain tasks later in the game (someone might walk slower, exposing you to elements or dangers more longer periods of time, etc.).
They are small things, but overall affect how the player plays the game. Therefore, it truly makes the game challenging for people rushing through the game so as to not simply adjust the casual vs. hardcore aspect with completely segregated options. Everything's intertwined.