Kate posted this, and it seemed worthwhile to me to start a new thread for it:
you know, it occurs to me that as you turn toward the idea of the non-linear story, something like The Elder Scrolls games might be interesting to explore. There is a definite story and plot... but it is up to the player to get there. In the most recent of these (Oblivion), you could take hours out exploring sub plots, tangents, and little flurries of story that had nothing to do with the main plot. Some people had trouble deciphering where that main plot started and stopped - and in several of the Elder Scrolls games, the game itself doesn't end when the plot does. You are allowed to continue interacting in a very changed world, sometimes still completing quests you had left undone for as long as you want. World of Warcraft (I know, I know) is another interesting idea when it comes to plot - every event in the story is somehow incorporated into Warcraft myth - every NPC has a past, every fight is explained. It is an ever evolving story, kept track of by players and developers alike - and you can look up any of those stories on a variety of websites dedicated to the game... and each of the instances has its own story as well (though there are occasionally gaps - characters revealed as being spies, enemies, etc... and standing around town again five minutes later, waiting for the next adventurer to discover the truth...) Each character you create has their own path they walk through the game from level 1 to 70 and beyond... if you just take the time to stop and read the quests when you get them. ;) talk about an unstructured plot!