So, like many would-be developers, I've played around a lot with games that build themselves. Let's talk about them a bit.
There are a lot of categories of algorithmic content. Some are very well tested and work great - for example, random map creation is very well done. There are many approaches and most of them work and have been put in games that are quite a bit of fun. Hell, "Roguelike" is a whole genre of game that relies on algorithmic map generation.
There are other kinds of algorithmic generative content. For example, the ever-popular Borderlands features randomized equipment.
So let's talk about how much self-referral the algorithmic content has.
In Borderlands you get random guns. The guns are just guns. Equip 'em, sell 'em, whatever. They don't really create any complexity, just variation.
On the other hand, a random map refers to itself. Each map segment is connected to other map segments. If you create random quests, each element of the plot connects to the next element of the plot. If you create random progressions, each phase connects to the next phase.
Typically, this is the weak part of algorithmic content. Any given chunk of content can be balanced and properly created, but when you start to tie them together you start to get a lot of complexity. In fact, in a game made by hand, the connections are often the most interesting part of the game.
It's not what the next room contains - it's how you're forced to face it, or how you have to work to get there. The transitions between the rooms.
Similarly, it's not that Alice is angry that is interesting in a plot point. It's why she's angry. What caused her to transition into that state.
Thinking of algorithmic content as simply balanced units of gameplay is a mistake. This is the core of the limitations the current algorithmic systems face: they think in terms of units of gameplay, because that's the obvious thing to think of.
If you think of a quest broker brokering random quests, you naturally start with the same assumptions: the broker will need to request a string of level-graded subcomponents. Kill ten rabbits in the D'e'tl'sle-fei'r' fields, then take a letter to H'eja'd'ifl's.
Instead, let's think of transitions. Each transition moves the player. It makes the player feel more emotionally engaged.
For example, the quest might start as "kill ten rabbits in X spot". The transition to that is player controlled, we'll just let that happen. However, we'll then have a transition where after you've killed eight rabbits, you are suddenly attacked by a vicious boar who chases you all around the level. The boar can only be killed by luring him into charging off a cliff.
See, this is a pretty basic pair of challenges: kill N enemies, beat boss. But the transition is what makes it suddenly interesting. There's a sudden jolt of panic when the boar blasts in from nowhere and completely shrugs off your arrows.
Surprise is low-hanging fruit. You can easily improve any algorithmic system by adding in elements of surprise. Collapsing floors, dogs jumping in through windows, whatever.
But there are lots of other kinds of progressions. A lot of them are simple pacing controls - a monster that stalks you from afar for ten minutes before it attacks. A treasure chest you can see but that it'll take some more rooms to get to. Secondary gameplay challenges mixed in with the primary gameplay challenges. Color notes mixed in with the gameplay.
A bit harder to tackle, though, is the player's emotional investment in specific characters, groups, or places. As an easy example: if a monster stalks you for ten minutes before attacking, it's going to seem a lot more personal and weighty than if you just get attacked out of the blue by the same monster.
NPCs, factions, and places don't have to vary wildly in terms of their mechanics or bonuses. You can build up loyalty and investment by having them act. They cause transitions which, in turn, causes the player to feel something about them.
If you are attacking a goblin fort and suddenly the elves stop by to rain arrows down on your targets, you'll probably feel something towards elves. If it was something you wanted, something that benefited you, you'll like them. On the other hand, if their arrows rob you of XP and light the whole place up as a giant fire hazard, you're going to feel that they are really annoying.
This doesn't require a delicate touch. There's no finesse required. Just understanding that it needs to happen, needs to exist as part of your random content is likely enough.
I guess I should probably go make a game like that, then.