Yup, the size of a rebellion depends on the size of the garrison. The bigger one is, the bigger the other is as well.

I thought it was butcher or something, that you got after killing more than 1000 people in one single battle. But I can't remember exactly.

As for the fact that you can't see a consistent behaviour in the govs of your rebellious provinces, you should take into account several things here:

1. if by "the more rebellious provinces" you mean the Portugal, Scotland, Lithuania, Livonia, etc., well, those are coded to be more rebellious. So even if your gov has a higher dread, the default rebelliousness threshold is lower for those provinces anyway, so you may still get rebellions even with a 5-6 dread gov. Remember, one dread is +5% loyalty, which is not really that much.

(Note: by coded, I meant in the prod_unit_11.txt file, or whatever it's called. You can change their default rebelliousness by hand, of course).

2. the vice(s) they have/get from executing or not executing rebels is (are) simply one (or however many) vice (s) out of the several that your gov prolly has. So you can't expect to see very clearly the effect of only one vice, in situations where other things are taken into the equation as well.
For instance, the loyalty in the province doesn't only depend on his dread rating. He may be a super-genocide-inflicting-psychomaniac, but if you have a crappy King, which is also faaaar away from that province, and that province is really rebellious, and maybe there are some enemy spies / assassins in it as well, and you don't have enough happiness buildings.... you'll get a rebellion nonetheless.
I think you get my point.