Dwarf Fortress does it, and it's awesome. I'm not sure how you would adapt it to a setting like No Man's Sky, though.
I think the problem is graphics. It's both easier and more time-consuming to fill a game with pretty graphics than to come up with procedurally generated history, economics, etc. That's why there are so many simple-graphics roguelikes and so many simple-graphics RPG's that provide incredible procedurally-generated content and incredible stories, respectively.
Another example where I think lack of graphics actually contributes to making a great game: Avernum (RPG). Way back when I spent hours of my life playing Exile 1-3, of which the Avernum series is part remake (1-3) and part completely new (4-6). I recently bought the last three installments and I've been having a lot of fun playing it.
The thing is, even until this day few games I've played came even close to the experience Exile/Avernum provides, both in the tactical RPG sense and world-building and storytelling, even though the graphics are quite atrocious. Most Triple-A RPG's I've played were nice in many other ways, but fell short in the crucial elements that I care most about.
Scroll down to the Donate section.
You could even have the player interact with the "bacteria" and alter the curves forever.Remember the savages you helped out at the great hunt with your blaster- well they conquered the planet and went to the stars "conquering" to honor you. Disclaimer: As with all generated content, the main problem is to have the players attention "the hot potato" wander on as fast as possible.