That's a great idea !!!
And I thought about a way to do it. Civ 4 Conquest has begun with it : scientific leaders. In this case, a scientific leader can appear when you are the first to discover a tech. You use it in rushing a building or add him into the city's scientific production. How about doing the same for all of the caracteristics ?
For science : Just a little change. Cities produce a certain number of science per turn, which you can change every turn. Let's say that a scientific leader will appear when you reach miles stones (such as 100, 300, 1000, etc). Those scientific leaders cann't be used to rush anything, just added to the scientific production of a city. Big scientific leaders would still potentialy appear when reaching a tech first, but those ones make you able to rush a building. But if you decide to add them to the scientific production, they should also give 1 cultural point per turn (or maybe a fraction, like 1 every 3 turns).
For culture : Same idea than science. This time, the mile stone might be culture per turn, as it doesn't change like science %. The caracteristic of the cultural leader shall depend on what brought the civ to mile stone. A great preacher for temples, a great athlete for a Colosseum, a pope for a cathedral, a great author for a library, a philosophe for a university and a researcher for a Research Lab.
For trading : Also same principle, but more like science. This time, miles stones should be an average of the last 5 turns' revenues. Just like science, that trade leader can be added to a city, increasing its revenues. Miles stones could also be when you are the first civ to have built a certain number or percentage of a certain trading improvement (markets, banks, harbors, airports and stock exchange).
For production : Same thing than culture. The leader increases the production of the city by a certain percentage.
For happyness : The building involved would be Aqueduct and Hospitals for sanitation; Courthouse and Police Station for security; Mass Transit and Recycling Plant for ecology. Those give out points and those points are the miles stones. The result of an emotional leader is both higher happiness in the city and a by turn party. This party can be canceled by war and happiness reduced.
For military : The Heroes can actually be used to form an army (what I recomand) or rush a building (what recomand for Forbidden Palace). They should also be used to be incorporated in a city, in order to reduce it's military building (units or building : City Walls, Barracks, Coastal Fortress, SAM and ,halfly, harbors) costs.
When added to a city, a leader can tell his toughts about the whereas of the civ, through a Leaders Screen (like the council in civ 2) or by a message between turns. This message would depend on the situation, like war or not, the tax/science/leisure percentages, the number of such buildings or units. For example, a scientific leader might say "There are enough Libraries. Let's build some Universities." a Military leader might say "We need to build more Artillery to protect our coast !". That Leaders' Council can be consulted every turns.
You can add a leader to a city, only if that city has the improvement that created the leader (science, culture, production and happiness) or a least 2 improvements of a kind(military and trading).
How about this idea ? It may complicate the game a little bit, but it would be pleasant to me.