OK so New Medium and Old Small are the same size. Got it. The oddball very small village is fine and easily dealt with, I just had not experienced a single building village before myself.
There still does seem to be, on average, a tendency towards smaller population villages, even with "Large" selected. I went through a couple hundred generations just for testing and I couldn't get 1 village population over approx. the low 2,000s. I used to be able to get a population of 4,000 - 5,000 without any problem at all, usually within a couple dozen generations. If it is still possible to generate villages of this size population then it seems to be much more difficult to achieve.