Back before 1.1, I made a Sovereign history called "Archeologist" which spawned a Lost Library near my starting position. This was for my own use to speed up the opening game. I figured that story-wise, as an Archeologist, my Sovereign searched far and wide across wide and barren lands for one of the fabled Lost Libraries of the former age, and at last has discovered one - and that is where your game starts.
Perhaps, building on this idea, each Sovereign history should have a related bonus. The only history I thought was unique was the Warlord history, which made sense to start with 2 units at the beginning.
Any ideas? Suggestions? For example, miners might start surrounded by mountains, with a mine nearby. Royalty might start with a city, or even be in the ruins of a city, perhaps being able to rummage for materials and other stuff.