Science: Education.
If you don't keep up education, you lose techs that have already been researched, thus making a dark age possible. It could be a function of research, since they are linked. There is an automatic subtraction of test tubes every turn, then you add all the test tubes you earn through research spending amplified by education. If research spending and education are not high enough the result is negative and a tech is lost. Most recent or random choice would do. Or it could be more complex, tracking which tech was being used or not used, ie your advanced civilization may forget how to work bronze. Random would be almost right, but what do you do about prereqs? The core of the game is competing advancement (which is why silly frozen scenarios miss the point) over time.
Definitely Not: Provinces
Provinces already exist and they are called cities. If cities and city spheres of influence are not enough for you, subcapitols such as you get with the forbidden palace are the same thing. What's really fun is to make all wonders reduce corruption like the forbidden palace, and have a high level of corruption generally, so its a contest of developing distant cities into regional capitols. Leaders become really valuable, since they can increase the size of your empire by one such "province" by putting a wonder on the frontier.
Something Else: Multiple Layers Done Right. When I first bought Civ3 in October '01, not having played civ before, on rumor that Civ 2 had more techs than the Aof E series(which I loved, but had gotten tired of--as I have not really gotten tired of Civ SINCE IT IS MORE FLEXIBLE WITHOUT BEING FLUID) I looked at the box and thought: "Wow, Sim City with war, Aof E with cities!" Then I saw the lame city view and was disappointed, then learned to appreciate civ for what it is, not just what I had expected. But still, it would be nice to have that level of detail possible, where you can concentrate to a realtime tactical level of control similar to AofE, once two stacks start slugging it out in the civ like cental strategy and development game, or you can focus tightly on a single city, between turns, growing it like a simcity city. This would add without taking away, something the Civ4 manifesto apparantly abhors, but as long as this forum is about adding dreamy features, why not.
PS. The detail views could be something you earn with a tech/gov. For example, a City Management tech could earn you the right to micromanage cities (but only benefiting from free enteriprse to the extent you have a free government); a Tactical Leadership tech could earn you the right to micromanage battles, and etc...Not only would this produce a cool effect of lifting the veil of ignorance with progress, but it could be done as a lucrative series of expansions that don't alter the core. "NEW and IMPROVED with Advanced Dipomacy tech--now you too can micromanage international talks."
Resources: Resources could be done a lot better, and this would be the key to many other improvements that would snowball into a lot of fun stuff like supply lines and therefore better naval. It would have to be done very carefully or it would be a mess, which is why its a perfect item for a dream sheet with supposed supergenius designers. I think that Conquest on Colonization of the Americas was on the right track, but the treasures produced by resource exploitation buildings could be resource bundles, but there should also be some way to like stop tanks that don't have a supply line to oil--ie a city which has an unexpended oil bundle (buildng?).
Illegal Pick Number 5: Secessionist splinter civs.
Illegal Pick Number 6: Simple AI Editing. I want to be able to improve the AI without having to get a degree to do it.