I have to say I have seen the other side of this as well, in a VH campaign game I have had London (as the capital) with a pop of 40k+ with a governor and 6 free militia units and very High taxes and still happy... Of course I had wiped out Scotland so have the British Isles to myself so I don;t think there where any enemy spies or armies wandering around. Small rebel stacks would occasionally appear but that was okay. I could also remove the governor without any real fallout.

I also had Antioch at the same time and it had a 45k+ population and religion issues plus enemy spies wandering around. But it was still controlable with a full garrison of 20 militia units and no governer provided I maintained a couple of priest in the province and a spy or two in the settlement.

But then playing as spain I was having all sorts of issues maintaining order in my provinces but with Moorish Imans and spies wandering around I think the cause was fairly obvious. One interesting thing is that you can have Religious Unrest even if the province is 100% catholic?!?!?