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)
Difficulty: Moderate-High
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)