Venice was over 50K population in my Byzantium game, and I had no problems maintaining control over it. However, it was not with 1 militia unit. I had 18-20 units in the city. The negative to public order from squalor caps at 80%. It was either 100% or 120% in RTW, so I'm finding this much easier to control.