Fallout’s Forgotten Revolution

An editorial called "Fallout's Forgotten Revolution on Hellmode points out the fact that Interplay's post-apocalyptic masterpiece brought us a non-linear experience a decade before The Witcher or Dragon Age: Origins showed up.
Approaching the camp during the day yields the choice to converse with the leader of the Khans. This conversation can lead to several possible immediate outcomes. If your Speech skill is high enough, you can either intimidate (through Strength) or persuade (through Charisma) the Khan to release Tandi under your charge. Lacking these skills, you can choose to bribe the Khan with some bottlecaps, knowing you are outmatched, outgunned and that you'll likely receive compensation for it from Tandi's father.

Armed with your companions Ian and Dogmeat by your side, you can kill him in broad daylight and offer the rest of the Khans a similar fate as you fight your way through the camp to rescue Tandi. Through force, you can raid their safes and loot their corpses as you emancipate Aradesh's lost daughter.

The other option is to proceed alone through the camp at night, and open the cell in which Tandi is kept, freeing her. Escaping the notice of the sleeping Khans, you can make it back to Shady Sands under the cover of darkness without spilling a single drop of blood. A more brutal approach would have you murdering each and every one of them in their sleep, slashing their throats as they remain blissfully unaware to your presence as the grim reaper. An even crueler option would be to plant cooked grenades on their sleeping bodies, timed perfectly with your escape for an explosive and gory mix.

It's more options than anything Dragon Age has to offer, and I haven't even mentioned how your decisions affect the endgame. Interplay designed the game in 1996, and released it in 1997 over a decade before Dragon Age saw the light of day. Fallout is the name of the game.
Let's not forget about the non-linear RPGs that were around a decade before Fallout, too, though. The earlier Ultimas are the most obvious examples, but there was also Wasteland and Fountain of Dreams (to a lesser extent), Moebius, Demon's Winter, and so many others.