Diablo II (the one I know), generates maps procedurally. However, the quests, weapon categories, general story, are all the same for each run. I'm talking about taking this concept up a notch. At the very least, have a new story for each run or player.