"Give me a large world with lots of complexity and I'll entertain myself for hundreds of hours."
Personally I'd say one of the problems is that No Man's Sky never had "lots of complexity" (not that you are necessarily claiming it did or tried to). Maybe I just know too much, but I can see through the algorithms generating all the pretty pictures pretty easily, and from there it's not hard to notice that the preconditions those algorithms have is going to make it so that pretty much nothing of any other complexity is possible. So you have all of these very beautiful worlds, where all you can do is point at things and shoot them with one of a couple of different types of beams. That was pretty much written in stone as soon as the data structures that make up the world were written down; there's not much more you can do with those data structures other than what the game offers you.
Contrast with Minecraft, which is built for interaction from the get go. It's a very different data structure.
Come to think of it, you could do worse than take an early Minecraft as your base and build No Man's Sky on top of it. (Modern Minecraft would be more like what particular worlds would look like; it's now a bit too detailed to build something like this on.) Another thing you'd get out of that is that you can build things that actually interact with the environment, the way villagers (who may not actually build their villages, but they do farm) and creepers ("boom") do in minecraft. Worlds could not just look superficially different, but actually have different behaviors in them, this world filled with creatures that aren't violent, that world filled with things that destroy everything you do as soon as you look at them, etc. If one was clever and could make those world rich in resources, perhaps even resources the peaceful worlds entirely lack, you might even be able to get some "game" going like having to land with a party to defend you while you put up an obsidian shelter or something.
Man. Suddenly I wish I had a few million dollars spare lying around because this sounds like with some care it could be hella fun. Make it an MMORPG somehow (biggest challenge: What game mechanism can you use to prevent too many people from being in the same chunks at the same time? Solve that and you're a great deal of the way there, since Minecraft itself pretty much proves out the rest) and you could have an Eve killer.
See also my comment: https://news.ycombinator.com/item?id=12276473#12276881