I think you are spot on. I have been toying with a formal theory about this stuff which I then turned into a rambling HN post. Here's what I came up with:
In my theory, the reason that NMS is unsatisfying is because it has great procedural generation breadth (PGB), but insufficient procedural generation depth (PGD).
PGB is defined as just the raw number of composable pieces that can be used to generate artifacts. So, how many plant bits, animal bits, biome bits, etc there are available to the procgen system. NMS has sufficient PGB, there are lots of bits.
PGD is defined as the influence or interaction between PG artifacts. The influence can manifest as either affecting the generation itself (a high-gravity planet reduces the maximum size of procgen critters) or artifact behavior (a dim star cold planet alters the critter behavior to reduce movement to conserve energy). NMS has neither, as far as I know. Human defined categories or tag metadata for PG elements does not count. Declaring that sets of procgen components are all "desert" is not an interaction. NMS has very low PGD, the animals, plants, and biomes do not influence each other. The devs have grouped components together to make biomes look and feel self-similar. But this was not done procedurally, and has no depth to it.
A game like Rimworld on the other hand has a lower PGB than NMS. By the numbers, there are far fewer variations of entities in Rimworld than there is in NMS. But Rimworld makes up for this by having much higher PGD. The procgen landscape influences climate and biomes. The biome and latitude will influence growing season which influences the carrying capacity of herbivores which influences the carrying capacity of carnivores. The procgen of the pawn's social and family relationships influence each other's behavior. The available calories on the map influence what pawns are able to eat - which will interact with their food preferences... The most important thing is that PGD makes the procgen entities actually matter and creates surprising stories.
(As an aside, It occurs to me that PGD is directly related to emergent behavior. It is possible that this could be formally proved, as conway GOL emergent behavior is entirely predicated on neighboring cells affecting each other. It might be possible to prove that any system with sufficient PGD is capable of emergent behavior: which is really what we want from a PG system. We want to be surprised by the unexpected, something that GOL is absolutely capable of. In fact you could probably use GOL as a starting point for this whole theory of PGD/PGB.... hmm....)
The king of PGD is Dwarf Fortress. It has very high PGB and PGD, and its ability to create surprising stories is legendary. My hypothesis is that this is _why_ Dwarf Fortress is so good.
Anyway, since NMS has no PGD, it has no emergent behavior (except by the players themselves), and you come away from it feeling that it is a mile wide and an inch deep. No shade though! It is a beautiful piece of work -- I have been playing it from launch, and I think it is a towering achievement (not to mention the most incredible PR story in gaming history). No Man's Sky is an outstanding work of art and it should be remembered for what it is, not what it could be (or what many people think it should be). And the emergent gameplay of the players is really fun too.
But when I think about what it might be like to have a higher PGD in NMS... it would be really something.