I actually liked the gameplay concept. There's nothing wrong with the concept for many people. The problem is that they failed to actually deliver the concept.
I think the difference between the concept and the reality does, however, lay bare a more important element. What most people want out of procgen isn't just that the algorithms can generate diversity... it's that they can generate scenarios that even the coders wouldn't have expected. Some algorithms can do that. Others cannot. NMS's absolutely cannot, they're just standard fractal noise terrain with random primitives, animals that are just armatures with random parts swapped out, etc. For anyone thinking of taking up the mantle of such a game after the failure of NMS, I think that's really going to be a key aspect. Because players are always going to explore worlds faster than developers can make new content, so if your engine is limited to making "things that the devels have thought of", it's always going to wear thin rather quickly.
The real world we live in always keeps presenting new fascinating worlds every time we explore a new place, for a key reason. Real worlds are built by fluid and rigid body interactions (primarily fluid, at least on the large scale) with variable chemistry. Physical properties like viscosity vary over numerous orders of magnitude in different pressure and temperature environments, and there's thousands of different chemical constituents that can be found in bulk, depending on the environment. Furthermore, each body is exposed to anisotropic conditions (bombardment, solar radiation, Coriolis force due to its rotation, etc), and widely varying local conditions like gravity. Basically, the computer equivalent would be CFD with chemical equilibria. Now, of course you can't do some extreme-detail CFD simulation of planets in realtime. But IMHO, if you want interesting generation, you want a generation algorithm that can emulate these sort of *effects*, even if the underlying core mechanism is radically different. Terrain generation algorithms generally make a goal of emulate the effects of uplift/folding, erosion, volcanism, impacts, etc. Recognizing how radically, many-orders-of-magnitude different these can all be in different environments, and with different materials in the same environment, seems key to making landscapes that can defy even creator expectations.
I think Pluto should be the gold standard. Before NH arrived, who would have thought that what we'd find was a giant scar facing Charon where the mantle bubbles out in supermassive convection cells, with mountain-sized icebergs drifting around the soup and collecting in iceberg-mountain ranges on the shore (just to name a couple of the really bizarre things New Horizons discovered)? The issue isn't "could you code a generation algorithm to emulate Pluto?"; of course one can. The question is, "could you code a generation algorithm that would have come up with things as weird as Pluto, without having to explicitly spell them out, without you ever having seen them before"?