Move random events away from being random and into being “choices”. For instance, an event that currently just random makes everyone go to war instead turns into a council where everyone votes on whether to have a war of finality or an emissary comes and demands you give them 10% of your income, if you fail fortresses appear on the map that begin attacking everyone.
Purely random events are great too and should still exist, they add interesting variables to the world.
But I've got a suggestion: there could be themed sets of random events that could appear in a particular game. For example, a "frost" based set of events - that come typically in increasing potency over the course of the game. Once a player realizes this he can adapt his strategy to cope with the event-set, as well as the world in general.
Sample sets: glacier frost world, demonic invasion, rampant hostile plant growth, low birthrates, spread of a religion, etc