No Man's Sky is kind of what you're looking for, except you may notice its quests (and worlds) become redundant quickly...I say quickly, but that became the case for me after like 30 hours of game play.
Procgen games mainly work when the procedural parts are just a foundation for hand-crafted content to sit on, whether that's crafted by the players (as in Minecraft) or the developers (as in No Mans Sky after they updated it a hundred times, or Rougelikes in general).
I haven't added any words or phrases to it in years, but I still use it regularly and somehow it still surprises me. Maybe the Spelunky-type approach can be surprising for longer; that is, make a bunch of hand-curated bits and pick from them randomly: https://tinysubversions.com/spelunkyGen/