The difficulty with algorithmic characters rather than scripted characters is not one of finding an algorithm. There are a lot of algorithms that work well enough, so long as you're not trying to do any natural language stuff. The problem is that the characters don't really have any depth. Of course they're going to be shallow and overly simple: they don't have decades of experience to make them complex! Haven't you ever seen Blade Runner?
So the real issue is how to inject depth into the characters.
The two basic methods are to script the depth or to generate the depth. Of the two, scripted is significantly better because it allows you to write in extremely deep things without needing to "back them up" with a full history or allow in a wide variety of muddying factors.
For example, if I want to make my game focus on the nature of honor, I can script in several different approaches for the characters to take. Not only do I avoid the need to script in some kind of system for algorithmically building honor codes, I also insure that the honor codes in the game are interesting and coherent to a modern audience.
"Scripted" doesn't have to mean painstakingly added for each character. If you script in the content once removed, you can allow characters to "grow" into the content. So far, the easiest way I've found to do this is using a simple system of memetics.
If you script in cultural memes, you can use a simple system of exposure to determine how strongly a character feels about a meme. While this can be done live, it is probably better to do it in a rough, approximate fashion while determining the character's associations, friends, living conditions, and so forth. IE, when you build the character, build his memetic framework simultaneously: don't try to simulate it explicitly.
In essence, this system means that if your parents are gamers, you'll catch the "gamer" meme. If your parents are religious, you'll catch that religion's meme. And so forth.
But this doesn't necessarily determine how you'll feel about a meme. The child of gamers might grow up a gamer... or he might grow up thinking gamers (and geeks in general) are pretty lame. Similarly, growing up religious doesn't mean you stay religious.
There's another scalar in addition to simple like/dislike of a meme. That's "obsession". Generally, the more challenged a meme is, the more you obsess about it.
What this means is that if you're a geek, but you're not obsessed, you're still a geek to the core. You just don't run around proselytizing. You're comfortable with the fact that you're a geek and other people aren't. If you're an obsessive geek, you tend to proselytize, and you tend to argue with other geeks of a slightly different flavor about which flavor of geek is best.
Similarly, if you're anti-geek but not obsessive, you're fine with the fact that there are geeks. You just don't think like them and don't like their stuff. On the other hand, if you're an obsessive anti-geek, you'll make fun of geeks and what they stand for.
There are some relatively easy models to control the spread of memes, how strongly you identify with a meme, and how obsessive you are about it. Adding in some noise is also a good idea if you're doing rough "backstory-style" meme generation rather than moment-to-moment simulation. I won't cover them here, because I want to cover something else before I run out of interested reader
The big issue with this is the same as before. Producing a world full of memes and then haphazardly plugging them into a character's mind will not produce a meaningful character. There needs to be a landscape of memes, and there needs to be an understanding that some memes are tinier than others, and can actually be simulated by noise.
For example, people who are geeks have an opinion on Star Wars. Some of them may be sick of giving that opinion, but they still have an opinion. In a game, this is unlikely to matter. It's important that geeks have internal disputes and agreements, because that affects how geeks get along from moment to moment. But it doesn't matter that it's specifically Star Wars or exactly what their specific opinions are. You could just as easily replace Star Wars with anime or linux or make up some random new thing that sounds geeky.
The only reason it would matter is if there is stuff in-game that is associated with a given opinion. For example, if you have Star Wars stuff in-game, you'll need to keep track of that meme explicitly, so you can have certain geeks that buy Star Wars stuff and certain geeks that don't. But it's extremely unlikely to matter whether a geek likes a particular brand of linux: it can be simulated by noise without losing anything.
Anyway, it's important to realize that there is a very strong correlation between some memes. Someone who thinks about linux to any significant degree is also going to have a lot of exposure to Star Wars and anime. They may not like Star Wars or anime, but they'll have an opinion on it, have thought about it.
This correlation is not really a result of any kind of inherent connection between Star Wars and linux. It's a cultural artifact, and therefore needs to be programmed in explicitly. One way to do it is to use umbrellas: there is a "geek" meme, and all these other memes are subordinate. Another way is to use proximity maps and radial expansion: the Star Wars meme is fairly close to the linux meme, and very far away from the sports meme. Someone can be interested in both, but only if they have multiple points of interest to radiate from...
Anyhow, the memes will obviously need to be scripted specific to the game world you're interested in creating. None of these examples are of any use in a high fantasy setting. There, your memes are going to be more likely about racism, magic, honor, nobles... whatever you want your game to involve. You'll need to custom-script memes for every world.
Because worlds are very complex, it will require a lot of memes to get characters to a "minimum complexity" of realism. However, you can take a lot of shortcuts: anything that the player character doesn't interact with at all can be simulated by noise or by faceless, largely random memes that he never gains any opinion about.
And, of course, there are two additional requirements for this.
1) The character AI has to be strong enough to allow the character's opinion to matter. If there is a dueling meme, someone who is pro-dueling should duel a lot.
2) The world has to "clump" characters that share memes together. Whether this is in loose social groups (most of my friends are geeks) or in explicit structures (a fan club) is not really important, except as a matter of flavor. The only important thing is that the "social map" of the world is "bumpy" in way that makes sense.