Cities!
One thing that hasn't been in any previous Paradox game is the ability to emulate cities without actually having the whole province. Thus places like Gibralter, the Indian colonies and Macao can't be shown properly. However if we had cities we could do this. Here's how it could work.
Cities would be the center of trade and of industrial production in an empire. The provinces would be the center of agriculture and the bastion of aristocratic power (and probably the center of manpower for many).
Cities and provinces would be linked as one. Together they would create the actual province as we know it, but in most respects would be independent of one another. Any improvements made to the city would not be mirrored in the province, and vice versa. However they would be interlinking at the same time, a rise in power of the city would proportionally undermine the province.
The main city would always stay the property of the province. Thus you would have to take over the province if you wanted that city. However there may be "trade cities" which are not owned by the province owner, but someone else. These cities would only be responsible for trading, and minscule amounts of production may be done in them.
All trade cities in provinces bordering water would have ports, but not all main cities would have them.
Trade cities could be protected by fleets only. This was how Indian colonies often survived their neighbours who had much larger manpowers, simply because cities were close enough for ships firepower to defend them. This would also make them more attractive to naval powers as their trading assets could be protected even against the most fiercesome land opponent.
Trade cities would get the bulk of the trade income from a province. IMHO a system similar to EU2's provincial trade income would be the way to go in any trade system for EU3.
In war, trade cities could be taken. I think a good interface for demanding a coastal city would be being able to demand peace, and then be able to click on each province that you want to take, and if you want a coastal city, you could click on that province's city.
For colonisation, I could forsee trade cities coming into their own. Trade cities would be what you would colonise with. You would comission a new city be set up in the province, but you wouldn't automatically control the province. Other nations could also set up trade cities there.
Slowly as the trade city grows, it would expand it's influence over the surrounding province. One nation would not be able to claim the province around it however until all other claimants to the province had been taken care of. New claimants would not be able to set up a trade city after a certain amount of the province has been influenced by other nations.
Following this for one moment, in the colonies taxation and thus the provinces would be very small amount of the income, if any. The main benefit of expanding to a province would be a better regional grip, and access to the agricultural production of that province. If, however, a colony grows really big, then taxation should become a factor.
Trade cities would be expensive to set up, and would at the start probably require extra crown funding. It would be very dependent on climate, and in cold conditions, at an early age, many would probably die if they do not get established well, and the trade city may die again. In other places disease could be a major factor as well. Any nation could try and keep these trade cities alive, but in some places the cost of maintaining the colony would exceed the trade income it would generate (Africa comes to mind here). I think it would be good if there was a slider available independent for each trade city that would determine how much money the crown gives to the colony to maintain or help it grow.
Trade cities could be set up in uncivilised (by european standards of course, this would be just about everyone not christian) nation's territory, however the maintainence costs would be higher (emulating any strife going on), and the province would not be able to be influenced into your rule, and would have to be taken by war if you wanted it. I was thinking also that some places would give more trade than others, and having a lot of trade cities in one area would devalue it, especially if they are from other nations. (It's good to have a monopoly isn't it?)

Also if you are on the receiving end of these trade cities as an uncivilised nation, it should give a boost to your production income, as there is a larger demand for your product. So while you lose out on trade heavily, it may be just as good to have them around.
Trade cities could perhaps even exert their influence over a whole area's trade, depending on how good that nation trades, and if their opponent also trades well. Trade cities would not get so much money in trade if there are no valuable products in their trading influence. I think this would well show that Gibralter wouldn't get so much trade as Goa for example.
Lots of stuff there, and it covers a few categories (colonisation, peace settlements and breakdown of power), but I think this would be an excellent way of modelling all those aspects if the model is well done.