Conversion seems to scale inversely to existing converts. But more priests means more conversion power. You can convert a large percentage in one turn with 10 priests (or better, cardinals, though it's their rating, not their title, that matters) if there are very few converts in the region. Once you hit 90% you see it's slowed way down even with those same 10.

Also, there's a good line of priest-enhancing traits for converting a large percentage of a region in one turn (I think the magic number is 8% off the top of my head). So it pays to have "god squads." They self-reinforce.

But there is also a line of good traits that comes from preaching to the converted.

And, yes, there are good ancilliaries in the cities with the right buildings. You can usually get them fairly fast.

My impression (not measured) is priests in the cities do not convert population. They also don't seem to become heretics.