RPG-wise, everybody talks about non-linear gameplay, on the other hand, branched game stories are very expensive and do not really add to the entertainment value of the game for the first play.
So I am currently thinking about simulating non-deterministic NPCs. This would work thus: A couple of NPCs with the same role (e.g. peasants) would appear in the game, but their AI would only be assigned when the user interacts with the NPCs, in exactly the order the user approaches them.
So, for the user it seems that he randomly picks an NPC to talk to, and that NPC happens to have all the details on the next quest.
For the game, the NPC the player talked to was assigned the personality / dialog / etc that was required to set the player up with a certain quest.