Short Version:
Optimizers work by removing junk from the map. So, the reduction in size depends on how much junk there is in a map. So your second question isn't a meaningful question.
On the one hand, you could have a 80mb map, but if 77mb of that is junk, then it will still be under 4mb after optimization.
On the other hand, you could have a 4.2mb map, but if 4.1mb of that is non-junk, then no optimizer in the world will be able to get the map size under 4mb.
By the way, the World Editor always inserts lots of junk into your maps. If it sees a map that doesn't have those junk files in it, it will get confused and be unable to open the map.
So really, map protection is just a side effect of making the map smaller!