Most games with random quests are just one basic objective and then return to base (if that). If they had just taken a little more time to add in more random branching components to their quests they would increase the longevity and fun of their systems exponentially. Making a system with many different types of objectives that can be interlocked in many fashions would make things a lot more fun, and with not too much extra work.
The goal should just be to design small, functional miniquests with a lot of random components, and then combine these miniquests together for a larger quest. With enough quest components it should be possible to never have the same quest twice and even similar quests would have their own quirks as well as likely being chronologically spaced far apart.
Here's a sample for the system I envision:
Whether totally random, or based on game specific factors, the game decides that it is quest time. The program then evaluates how far the game is along, the strength of the player, the resources available to him and then decides on the quest length. In this case the program decides to create a long quest based on the players empire size and previously assigned quests. The quest isn't going to have you create an iron golem if there isn't an iron mine in the entire map. It also would be unlikely to do so if iron did exist, but was extremely hard to exist.
The game randomly decides that the focal point of the quest is a large monster. It spawns a large, powerful monster (from a pool of many). The game selects from many back stories on why this monster is here and presents the player with an immediate decision to make (not in a multiple choice menu, though this is an option too). The monster will ravage a small section of their land for a long period of time. They can either try to:
-Ignore it and take the damage
-Try and lure it away to someone/where else (could involve a subquest in itself to trick or charm the monster).
-Attack it with brute force (Monster intentionally made strong enough that this is usually not the best option).
-Follow the standard quest line.
Create a group of 100 Knights (The knights are chosen because the player has the resources to make them, but not trivially so. The game could have chosen 150 knights, or it could have chosen 50 crossbowman. The harder the goal, the more the internal difficulty variable for this entire quest line goes up. Adding the option for the player to "raise 100 knights or 200 crossbowman" will provide even more player choice. Player would be presented with the back story that these are men whose homes/livelihoods have been destroyed and are looking for vengeance, which would be one of many possible reasons for recruiting the men. Another quest might not even care how you get them, so long as acquire them through some means).
Slay a den of monsters using those units as part of your force (As before, this could be any group of monsters either in existence or spawned just for this quest. The monsters could even be substituted for killing a generic amount of X monsters or Y amount of another players forces. Lots of possible back stories here.)
Though created from random parts this permutation has a lot of benefits normally only found in entirely hand crafted quests, such as:
The player is given choices right from the start and they aren't forced to do anything.
The player's game is spiced up by this random problem they have to consider, but with very clear ways to rid themselves of it (instead of feeling powerless and apathetic about a hurricane hitting their lands). They can solve this problem, and be rewarded. The problem is happening constantly and visibly. They will see the consequences of their actions or inaction.
The player is continually given some amount of choice even after they decide their initial approach to the problem.
Combining the removal of a punishment and an the gain of a monetary/magical reward is psychologically a great feeling for players who slay the beast. Quests of this length should always feel like an accomplishment.
Though each component on it's own is fairly generic and simple, the chance that that same player will encounter the same steps in the same order is very slim. Even if they or another player does get the same sequence of events, the random and situation specific factors of each component will likely make it feel very different, especially if entirely different back stories are chosen.
Of course some components might need to be more specifically linked to other components for them to be logical, but there's no reason why this system wouldn't work. It's beautiful because of how extremely moddable it is. There's nothing to stop anyone from adding a few new components or expanding on existing ones. Even an inexperienced modder or someone with little time could still contribute a quality component or back story addon to add more content to the game.
There's also nothing from stopping unique hand tailored quests from being incorporated alongside this system.
I also appreciate how if this system is done right that there will be such a huge variety of quests that we won't have players save/loading constantly trying to get that 1/5 of quest types they like. They'll be no guarantee they'll get anything close to a previous quest. Additionally, all the objectives of a quest don't have to be revealed at the get go so players won't really know every step until they get there. They can't just see that they don't like objective number 4 and load a saved game.
Some of you might be thinking this is far too complicated. It really isn't that hard to automate. From the coding perspective it just starts with a problem and a goal and works backwards from that goal to possible solutions, to possible ways of achieving those solutions and so on. The general look of the quest is shown below with alternate example options shown in parentheses.
Main Goals: 1 (Any number, by usually less than 1-3)
Goal1 Type: Monster Spawn (Invasion, Delivery, Exploration)
Goal1 Subtype: Rampaging (docile, wandering, moving from point A to B )
Goal1 Solution1: Expose weak point & slay (recruit, slay, charm, banish, appease)
G1 S1 Mechanism: Use quest item (cast spell, use ability, use normal item)
G1 S1 Mechanism acquisition: combine items
G1 S1M 1: Loot off specific group of monsters (loot off random monsters, loot off unique monster, no special means)
G1S1M 1Subtask1 - Recruit units (locate information on targets, search for specific target, amass X magical creatures)
G1S1M 1 Subtask1 Subtype- Acquire X knights (recruit/create vs acquiring, knights vs other unit types, different amounts required)
G1 S1M 2: Previous quest reward (common item, rare item, spell)