My question is, how many people lived in a medium sized European village (like Germany) in the year 800. And how many people would have walked on the streets in a daily routine?
The book The Medieval Village, by George Coulton, has some information which seems to provide a basis for calculating an answer to your question.
According to the first column of information, in the year 800 there were an estimated 100 Villages in this region. These contained an estimated 20,000 individuals, so we can calculate your average village size of 200 people. Note the next column for the year 900 these numbers all more than double, and the average size has climbed slightly, to 240.
At a similar time villages were starting to make an appearance in England as well. (I know this question directly specified Germany, but the theory behind villages is connected.)
A series of lectures I have been watching on the history of English architecture, conveniently has a transcript so I can show you a related section from the lecture Making England: The Shadow of Rome, 410-1130, by Professor Simon Thurley CBE.
Before the tenth century almost everyone lived in scattered settlements of no more than a score of people. But between the tenth and twelfth centuries, in the central arable areas of England, peasant farmers abandoned their farmsteads and hamlets and moved to create villages. These places normally had a church, a main street and between twelve and sixty houses.
If we just toss an average number of 6 people per household (I know, needs sourced, but we are just shooting for an average here) we get 72 to 360, with a median of 216. these estimates seem to correlate fairly well with the above figure.
So average village size in the medieval time period from 800-1000AD seems to be falling in the range between 200 and 250 people. Information on both German and English villages seems to indicate similar sizes in both regions.
Rather than try to argue fuzzy things like the meaning of "Medium Sized", how about I give you some stats?
According to McEvedy's New Penguin Atlas of Medieval History, in AD 737 there were only 3 cities in Europe larger than 15,000: Toledo and Salonika (both in the 15-22k range), and Constantinople (in the 50-125K range). None of those cities were under the authority of the Pope in Rome. Toledo was part of the Umayyad Caliphate, and the other two were Byzantine. The entire population of Europe (as per McEvedy & Jones' Atlas of World Population History) had dwindled down to only about 29 million, from a height of about 36 million at 200 AD.
So that should give you at least a good ceiling for what should be considered really large in that era.