Starflight (1986)
I found my record-album copy of Starflight! (While I was looking for something else, naturally. It was inside the Age of Empires collector’s edition box for some reason.)
Staring development before the release of Elite, Starflight had a rather different philosophy for procedural generation. You see, instead of generating a few trillion galaxies, it generates about 800 planets. Since the game came on two 360K floppy disks, this was rather a challenge.
It uses a fixed seed, so that every game has the same planets. It also remembers your actions, so that minerals you collected would still be gone if you returned.
Where it really stands out from its contemporaries is the story content; with a lot of surprisingly deep interactions. Combined with the on-planet gameplay, which is the part that uses the most procedural generation, this has been incredibly influential influential: the planetary exploration against the backdrop of an epic sandbox story is the prototype for everything from Star Control II to Mass Effect to the Forgotten Beasts in Dwarf Fortress.
These days, you can get a working copy of Starflight on GOG, which is way easier than the rigmarole I had to go through in the ‘90s when I got my second-hand copy. Do back up your save games though.