Well take it back to the Dune reference. (Writing this up and I'm realizing how long it has been since I actually read the books. Assume that the following contains spoilers and mistakes, but close enough to get the gist for game design.)
At some point the Emperor was faced with Liet Kynes and the decision as to whether or not to allow him to start doing his massive ecological survey. This decision becomes a branching point in the Dune series with various possible outcomes. Allowing him to go unlocks a route that potentially enables Paul to overthrow the Emperor far down the road, but denying the request to start the research might either close that story branch or open a new one where Liet Kynes meets someone at court and and whole other chain of events might start to unfold. Maybe he meets up with a group and an assassination plot begins, or a plot begins and he discovers it and saves you.
Depending on how you are doing in the strategy side of things then different storyline events may trigger. Have you just failed to suppress a rebellion? Then you've met conditions under which different events may trigger, possibly so and so in a neighbouring sector will rise up and lead another rebellion because he sees that the empire is weak. Or maybe person such and such will rise up in the recently rebelled provinces with a counter-revolution, because your previous story line choices gained favour with her and her family, and she feels that her people are better off being in the fold of the empire rather than on the edge of it.
Your story scripting would ideally include chances with which ways given choices swing, simply to keep it hard from trying to repeat the same game twice in a row.
The core choice you have to make is, how big is your cast? How many factions are there? Do you want "Random" people to come up and be generated at runtime, or do you want to keep the storyline to be tightly focused with a dozen or so 'names' weaving the story around the emperor?
Also, what story do you want to tell?
As for your random factors, they can be a simple as laying out options in the script. Option A has a 50% chance of firing, B 30%, C 19% and D is 1%. User might see some of the odds when making a choice, or they might have the odds and effect hidden from view. The point of the random factor would be to add some flexibility and surprise into user choices, and some risk/reward. If Choice A always has a more positive out come than Choice B, then you'll want to pick it. But if Choice B usually is worse than A, but has the chance to be far far better on a good dice roll, then maybe you'll take it on some games instead, depending on how things are going for you.