Dienekes Pontikos ruminates on the changes in human genetic variation on a world-wide scale over the past 10,000 years based on an MDS plot of East Eurasian genetic variation which he generated. I've taken his plot and added geographical labels, so you can see the difference in scale between geography and genetics in terms of distance:
What this plot shows, in tangible form, is a picture of mankind's past: before the invention of agriculture, most humans lived in small tribes, scattered across the world. We can be fairly certain that the action of genetic drift and natural selection would have created a cornucopia of human diversity, with high between-group diversity due to high levels of genetic drift. Out of all this variety, some tribes of hunters made the transition to agriculture, growing in numbers, filling the areas they exploited, and expanding into new ones. The hunters were on their way to extinction, but new tribes formed at the fringes, those of pastoral nomads exploiting animals to thrive where neither farmer nor hunter could. In the world of farmers, with growing population densities and expansion came the breakdown of isolates: this led to a further homogenization of the farmers' gene pool, as different tribes that had adopted the new way of life lost all trace of their past tribal identities and formed new ones based on the common language of the agriculturalists and the new way of life. With more human bodies in the farming communities, came more novel mutations, and hence more of the raw materials of selection. Coupled with the new challenges of agriculture, for which man is unaccustomed to, the social challenges of living close to many others in villages, and, later, cities, the cognitive challenges of new symbolic systems of communication, selection further reduced diversity in key aspects of human appearance and behavior, while maintaining it, or even increasing it in others, such as resistance to pathogens. In western Eurasia this process was pushed to its limits, and there are virtually no nomads or hunters to be found there anymore. Africa was explored by Europeans just in time to find living hunters such as the San and Pygmies still in existence there. A few centuries more, and perhaps they, too, would have beeen absorbed into the mass of expanding farmers.
I pretty much agree with this. Intuitively this seems to jibe with reports of strange looking peoples in the mythologies of many literate civilizations. One plausible explanation for trolls, witches, and fairy-folk is that the human mind is inventive, and perceives mystery and agency all around us. But another seed of these legends may simply be the conventional human tendency to de-humanize other populations. In World War I you saw a perfect illustration of this, as Americans were told that the Germans were "Huns." This de-humanization occurred despite a substantial minority of Americans being of recent German ancestry at that time, and the Germans and Americans themselves being relatively culturally close (the American colonies were after all ruled by a dynasty of German origin just 150 years before).
Before the expansion of agricultural peoples within the last 10,000 years perhaps there was more phenotypic diversity than we're used to seeing around us now. As first-mover advantage allowed for the rapid demographic expansion of some groups into the "frontier" they may have absorbed or assimilated peoples of a far different countenance than themselves. One of the best examples of this seems to be the Ainu. These people retreated to Hokkaido by the historical period, but it seems likely that their near relations, the Jomon, were the indigenous people of the Japanese islands, only driven north or absorbed within the last 2,500 years by rice farmers from southern Korea, the Yayoi. Here's the received wisdom from Wikipedia:
Direct comparisons between Jōmon and Yayoi skeletons show that the two peoples are noticeably distinguishable...The Jōmon tended to be shorter, with relatively longer forearms and lower legs, more wide-set eyes, shorter and wider faces, and much more pronounced facial topography. They also have strikingly raised browridges, noses, and nose bridges. Yayoi people, on the other hand, averaged an inch or two taller, with close-set eyes, high and narrow faces, and flat browridges and noses....
When European physical anthropologists encountered the Ainu in the 19th century the standard assumption was that these hirsute people without epicanthic folds were a "Lost White Tribe." Genetic science in the 20th science debunked this inference. The Ainu are an East Asian people, and resemble other East Asians far more than Europeans or other populations. But, their physical appearance clearly was atypical. The reality is that the "typical" East Asian physical appearance is probably a function of the demographic expansion of the Han, and later the Yayoi in Japan. As the "world became flat" it looks like there was a "winner take all" dynamic at work.