I agree with much of what has been proposed here. The REF should increase based on a combination of time/difficulty/game-length-setting as well as some calculation of rebel-sentiment/rebel-soldiers/cannons etc. I think difficulty level is crucial here -- who needs to be facing a 500-unit REF at Pioneer Level?
However, if I were to dream up an additional feature here, it would be this: Add back in the wars in Europe (from COL1). When wars occur in Europe, the current-REF gets involved. Imagine if this were a CIV game -- the REF isn't just sitting around waiting for rebels to pop up for a few hundred years, it would run off to invade/defend-against the neighboring powers based on relationships among the kings. Similarly, wars in Europe should necessarily spill over into the colonies -- until you rebel, you are a vassal of the crown and must fight their wars for them (or suffer consequences); though, with communication delays, this may take some time to occur. Same with the other colonies.
Basically what this would add is, during the game the REF could get reduced (and some of its units add promotions too). ALso, the REF comes to YOUR aid if someone else's colony attacks you (i.e., spillover of a colonial war to Europe -- it has to work both ways, as you are a sovereign colony or there are consequences; e.g., King refuses to help you in the colonial wars, your rebel sentiment gets a big/free one-time boost which is untied to REF production, though REF can continue to increase later in the usual/modified way). Similarly, tax increases due to European wars are inevitable. But I think the REF should not magically recoup its lost units if it gets losses in its other colonial/European wars.
An additional step, probably for a penultimate type mod, is to have specific zones on the map which represent the various European-waters of each major power (i.e., this is the only place you can sail to England, not just sailing off the tip of South America and getting to England too) -- if they go to war with each other, they send their MoWs to each other's waters to attack the merchant shipping, in addition to sending them to colonial waters. So, your REF navy can provide you with protection, or refuse and your rebel sentiment increases.
Lastly, to flesh this out further, the European powers should have their own political dealings (+/- relations with each other, "you sank my merchant ship" stuff) like in CIV. And war weariness. Recall that that was a factor for England in the RW WoI. If the REF has been fighting the King's wars for 200 years, then gets called on to put down some unwashed rebels, well maybe they aren't too motivated for that and suffer a strength penalty due to war weariness.
Hmm, but how to control the units doing the intervention... You request units for assistance against native/colonial-attack -- does the AI give you some REF units for your use? Then you give them back after hostilities are over? Or the king lets you keep them if you have good relations? Otherwise, the AI must control them -- how would it do this competently? Say your merchant ship is sailing to Europe, there is a war going on, it needs protection -- how do you group your ship with an AI MoW to sail it to Europe? Similarly, a shipload of soldiers are sent to help you fight the war in the New World -- where do they go? what is their mission? do they go to your capital and radiate out from there on their own? or can the AI determine where enemy units are (from your known map) and deal with them that way? It is like being a vassal or ally with the AI in CIV, but with complication: it is one thing to have to hold your own until the king's troops arrive to help you in the New World (and have them arrive and do something reasonable at least for them if not for you or not in a timely manner), it is another for those troops to say sail around randomly because the AI is incompetent.