Because of your reminder, I'm listening to the FF6 opera right now in my mind, even though I haven't heard it for years. (Celes: "Oh my hero, so far away now, will I ever see your smile? Like night into day, you're so far away, it's just a fading dream."), so I understand what you mean very well about shared experiences and the like.

It sounds like you understand the weak points of procedural generation quite well, so I think you'll be able to use it to full effect and create a great game. Good luck! :)