I was designing some village-generation algorithms when I realized something that I don't think I've ever seen explained, although it's quite obvious in retrospect:
The complexity of your NPCs is limited by the state density of your NPCs.
As you may be aware, having loads of anonymous clones as your NPCs limits the appeal of any given NPC. Normally, they won't even have much unique content programmed into them. Even if they are shopkeepers or whatever, they will normally act to add only a tiny modicum of flavor to the world. On the other hand, having unique NPCs results in each of them typically having a lot of character and a lot of interesting things to do and want and say.
The example of this I tend to come back to is Beyond Good and Evil. While it had a number of nameless, pointless NPCs, it also had several extremely minor NPCs that stood out and were interesting despite not having any real complexity or adding anything to the game.
The obvious example is the catgirl in the resistance, who has I believe two lines, neither of which is interesting. But people still remember her. I also remember the two racers in the Akuda bar who didn't like you any. And Peepers, and the kids at the lighthouse, and the rhinos at the garage - these are NPCs which literally had as much dialog and story influence as random NPCs from open world games like Oblivion. That is to say, not very much. But because they were unique, they were a whole lot more memorable.
That is the part everyone realizes. Clone NPCs are boring, no matter how you write them. Unique NPCs are interesting, no matter how you write them.
It's important to realize that clone NPCs aren't just boring because they're written boring: it's actually really hard to remember them. If a wife tells you she's sick of her no-good husband always going to the bar, you're probably going to forget she exists by the time you get to the bar!
That's the basic, the obvious, the thing everyone knows.
What I discovered while making my village generators is that it's not simple uniqueness that makes an NPC able to hold more complicated relationships. It's more - something I call "state density".
State density is not just how an NPC looks, but all memorable aspects of them. For example, if you have a kind of dating sim game where the locations are poorly defined background images, those characters aren't going to have the same hooks into your memory as if they are in a Mario-like game and you're actually walking into their house and talking to them in their physical house. If the house's contents are unique or interesting, that's also going to make them more memorable.
Another aspect of state density is how frequently they come up. For example, an NPC who stays in a back corner of a house that you rarely visit is probably going to be forgotten. One that is always hanging out on the corner of main street will be more memorable. One that contacts you by radio every five seconds to tell you that you've entered a new region or found a new item is going to be extremely memorable, although perhaps not in a good way.
NPCs that can be altered also have an advantage. If you can move an NPC to any quarters you wish, they will be more memorable. If you can force them to dress up in various stupid Halloween costumes, they will be more memorable.
There is, of course, a "maximum active NPC count" that a player will be able to remember. However, I don't believe this is a big problem: if you want to use loads of NPCs, just arrange them in clusters so that the player doesn't run into a lot of NPCs when he's busily thinking of the ones he's just now talking to.
Anyway, just thoughts on NPCs.