So I'm currently working on the part of my game involving how special locations in each province influence the nations that control them. I have a lot of options here and I'm not sure what my plan is yet.

I could allow the Explore Province button to have a random chance to find a location and then a random location would be generated. If you pass the check it is added to your province, this system is I believe the one used in King of Dragon Pass.

I could also have a random discovery chance to find locations pre-assigned to your province, or a skill check of some sort. This is what Dominions 3 and 4 use.

I could assign a time value to expeditions and/or an exploration team size value, or possibly modifiers based on characters. For instance exploring with your god/ruler giving a good boost to finding chance and site quality. I could also have a 100% chance of finding something, with a minimum time value, and have time or size or characters on the expedition increase the quality of the found site.

The trade off here would be to force you to choose how to deploy your major characters, mages/scholars/god/ruler/explorers, and or portions of your population added to the exploration party. What major character you use may also determine the type of site, for instance mages finding magic related sites, scholars finding libraries or ancient castles and so forth.

A major goal for this system is to be a source of character for your nation. What you find in exploration could determine the way your nations goes. If you invest a lot of time and characters on a search and you are magic heavy, you could find an ancient mages guild of pyromancers with lots of fire related artifacts and tomes. From then on you would be a fire themed nation. Or you might find an ancient forge, causing your people to be great weapons/armor smiths. Or you might find the last enclave of a dying race and incorporate them into your nation. You could decide to keep them separate, to interbreed a little to keep them pure but stop them from dying out, or interbreed extensively so that your people would have a low level but noticeable portion of their unique traits. Maybe you find a library of an ancient agricultural society with books and seeds giving you high staple crop production and the ability to grow small amounts of rare crops or even crops thought extinct. As a last example since I'm getting this list really long, perhaps you find a hidden dinosaur population and use them as beasts of burden or war mounts.

In any case the goal of this whole system is to maximize the potential of the above concepts. In games like dominions you may get the ability to recruit a special unit, or a supply or rare magic gems, but that doesn't really massively impact the essence of your nation, especially as you have such a strong starting flavor for each nation. Also I'd like to give the player more freedom, so that finding the equivalent of the Abyssian's Smouldercone doesn't lock you on a path forever like your nation choice in Dominions3/4 does.

The overall goal of the game is to give you control over the fate of your nation even if you are still affected by the factors you don't control like province locations, what nations around you do, and so forth.