That actually sounds really cool. I haven't played the game, but generating unique personalities is on my to-do list. Would you mind explaining in a bit more detail how it worked exactly?
I might use a very multifaceted conversation tree for the actual conversing, but I'm still looking for the intermittent step between the star-system-to-star-system navigation, and the conversations with individual aliens.
It was basically a fly-around-and-trade space game, but since the combat was pretty rudimentary it was largely a game about conversation. You had a big starmap, and could fly to any planet, and around planets you could hail ships/planets/stations or be hailed by them. Most of the details of what you'd do (buying/selling, getting and trading information, etc.) were themed as encounters with specific individuals (captains of ships, planetary representatives, etc.) Like in Star Control 2, all contact was remote; you don't go onto their ships/stations, nor they onto yours. I think after conversations there may have been an animation representing cargo transfer, but otherwise it's behind the scenes; there's little doing that isn't talking.
Captains/representatives were represented by talking portraits and generated "speech"; you had the options of asking them about things, telling them facts in hopes they have something more to add, offering items in trade, and requesting items in trade. Each option was just a big list, and as you learn about things in this world, they're added to your list. You can ask/tell/offer/request anything to anyone, so long as you know/have it; your choices aren't limited based on what will be "relevant" to any particular person. (The lists get pretty big, which was annoying, but we're rather better at user-friendly lists today than we were 20 years ago. Immediately approximate search would be very handy if it's a keyboard-controlled game, for example.)
I should note that the interface itself is bland, but you don't really notice because of the charm of the aliens themselves. There were about a dozen alien civilizations, each one pretty distinct. Some are interested mostly in trade, others (like the energy beings) more interested in information, some only are willing to talk after you've fought a bunch of them, one you can't talk to at all without a translator mechanism. Each has things it wants, has, or knows about; the big drunken bears mostly are interested in trading food and drink, others mostly trade in military hardware, etc. Most individuals of these races are just generic instances, but there are also maybe a few dozen distinct individuals with preferences/knowledge that their compatriots lack.
While this was all scripted, I think a lot could, in principle, be generated. Each race had an animated portrait, a background (entirely forgettable, actually), a spoken language (just audio samples pieced together, but nonetheless a big part of the charm of the game), a few linguistic quirks in the text, racial needs and desires (like what they eat and like), and common racial knowledge (like their history, where their own planets are, what they think of other races). Individuals (that is, people representing ships/stations/planets) also have inventories (determining what they'll trade with/for and how valuable something is to them at that moment), and sometimes specific needs , opinions, and information (they might know a little-known fact, or know where someone important is, or need a particular item, or be unusually fair-minded about their racial "enemies".) All of this could be potentially generated. Some of it would be quite easy, others (like portraits, "languages", and individuals' knowledge of and attitudes towards other individuals) more difficult (but much more fun to do).
The reason I think that you could generate something like Nomad, but not generate something like Star Control 2, is that your practical inability to query everyone about everything leads to an illusion of depth. The keyword you haven't tried, or the keyword you don't know yet, might be the key to unlock more interesting stuff. (Even after you know that basically all drunken bear people are the same "person", you can still maintain the illusion that it's just because you don't know what to ask drunken bear people about that would differentiate them.)
Actually, that's another thing that makes the illusion work, is that everyone's an alien. If they were humans it'd be more clear that these were bland clones of each other with mostly cosmetic differences. The Outgroup Homogeneity Bias can work in the game's favor: since alien races are outgroups, individual aliens looking & acting alike confirms the player's expectations, whereas if they were themed as the player's ingroup (that is, humans), them all looking & acting alike would break the player's expectations. (Star Control II also took advantage of this; the humans and nearly-humans are very few and scripted as distinct individuals, because this is where people would find homogeneity to be immersion-breaking, whereas sentient mushrooms can all act alike and no one will mind.)