Some of this post incorporates ideas suggested by others. I hope no one is offended if they see their ideas in this post, rather they should feel complimented. Some of this is in indirect response to others comments. And I also apologize for the length of the post.
Number of Cities per Province
Provinces should be able to include any number of cities, from 1 to your entire civilization. Provinces could provide two (or more) benefits, increased contentment (happiness) and decreased corruption (or increased efficiency). The fewer the cities in a province, the more efficient they all are. The greater the number of cities in a province, the higher the number of content citizens per city. Both of these ratios would be curved so that the maximum benefit of both is when three to six cities are within a province. Cities beyond 7 tiles from the provincial capital would experience a more significant level of corruption.
Province Creation
The player should have complete control over the formation of provinces (within the rules of course). Provinces are optional. You can use them or not. A City not in province would be treated as if it were a province of one city. Creating a province is easy. Build a Provincial Capital (which requires an upkeep cost) then right click on any other city within the contiguous cultural boundary, not isolated by other provinces and select the name of the province (a list of provincial capital city names).
Removing a City from a Province
Removing a city from a province is not so easy. This would cause unrest and unhappiness in all cities with in that province, similar to when changing governments. Separating captured provinces or cities from those provinces and reassigning them should cause long term discontentment. England, France and the Dutch carved up Africa (and I think the middle-east) hundreds of years ago and there are still ethnic battles within countries. Another example is England purposely splitting up ethnic groups in India, Pakistan and Afghanistan. Ask an Indian or Pakistani to whom Kashmir should belong. The warring factions in Afghanistan can also be attributed to this.
Government Affects
Types of government system could also affect the effectiveness and influence of provinces. Provinces affects would be most pronounced within free systems like Democracy, and most inhibited in systems like Communism.
Rebelliousness
The relationship of a province with that of the civs capitol (the one with the palace) should be primarily within the players control. The number of and types of improvement differences should play a big part. Not having a library in a province when the capitol province does would be a minor rift. Not having a library or university would be a significant point of contention and none of the above or a research lab when the capital city does will definitely draw the ire of the neglected province. Them government rulers is keeping us down and aint learnin us nuthin. We is a rebellion! Or the other way, The unenlightened, illiteracy of our government is unconscionable and rational sovereignty may only be had by secession.
Creating a greater number of military units will also add to the unrest.
The affects are cumulative.
The rebelliousness should be insignificant for very small populations and magnify as population increases.
Assimilation
A province which has no rioting cities for 30 turns plus ten turns for each city in that province will be considered culturally and ethnically assimilated and poses no threat of seceding. Ex., A province of 5 cities would take 30 + 50 = 80 turns to assimilate. Like Hessians and Goths becoming German.
A lone city, with no provincial capital will not assimilate.
Bonds
(maybe this is not such a good idea)
With the discovery of banking, cities within a province may send some shield production (10%) directly to the provincial capital. Another 10% would be lost due to interest, leaving the other cities in the province with 80% of their shields for production.
Resources and Luxuries
If quantified resources and luxuries will be implemented, there should be bonus or special access to resources and luxuries within a province.