Prior to first contacts, Europeans didn’t speculate about the nature of Indigenous Americans for the simple reason that they had no conception of a distinct American continent with its own inhabitants. Famously, even some of the first European invaders (such as Columbus) maintained that they hadn’t reached a new landmass, but rather outlying portions of Asia. Earlier, one of the leading theories among medieval Scandinavians was that the Vínland described by their forebears was part of Africa.

However, there was an abundant history of European speculation on the inhabitants of distant, poorly-understood, and sometimes purely mythical lands. These became coupled with debates over the Antipodes--the opposite points on the globe, roughly the Southern Hemisphere from a premodern European perspective. Additionally, there were traditions in several cultures of fantastical islands off in the Western Atlantic. When Europeans did reach the Americas--beginning with the Norse voyages around the turn of the first millennium CE, and, later and much more catastrophically, with the Transatlantic journeys that began at the end of the fifteenth century--these concepts about the inhabitants of far-off lands significantly affected European perspectives on the people and societies that they encountered.

The bizarre beings that Europeans ascribed to distant countries are often referred to as the “monstrous races.” This is a problematic term in contemporary discourse, of course (see Asa Simon Mittman, “Are the Monstrous ‘Races’ Races?” postmedieval 6 (2015)), but it remains fairly common in scholarship. The monstrous races fall into a few broad categories. There are some who combine human and animal features, such as the cynocephali (dog-heads) and various merpeople; some whose essentially human anatomy is distorted, such as the monopods who hop around on a single large foot, or the variously-named “headless men” whose eyes and mouths were located on their chests; and still others who differed from normative European societies primarily through their customs. These included groups such as cannibals and Amazons, the latter understood as nations in which women fulfilled the traditional roles of political and military leadership, and men were either entirely absent or reduced to servitude. Naturally, there was considerable overlap among these groups; cynocephali and “headless men,” for instance, were often conceived of as cannibals.

Several of these groups are alluded to in the works of Homer (8th century BCE?) and Herodotus (5th century BCE), but their systematic categorization is generally attributed to Pliny the Elder (d. 79 CE), in Book VII of his Naturalis Historia. You can read this here (https://en.wikisource.org/wiki/Natural_History_(Rackham,_Jones,_%26_Eichholz)/Book_7). Having discussed the nations of the broader Hellenistic world in Book VI, Pliny turned in this section to people “living more remote from the sea”--that is, distant from the Mediterranean oikoumene. Drawing on a number of earlier authors, he located one-eyed barbarians, cannibals, and other monstrous folk in regions such as the far North, the Central Asian steppe, the Himalayas, and Subsaharan Africa. To be fair, he also sited some human marvels closer to home--the Hirpi clan, for instance, who lived just north of Rome, could walk on hot coals without being burned. But by and large, Pliny solidified a correlation between geographical distance and human polymorphy that proved indelible. The Naturalis Historia, and works based on it, were widely circulated throughout the subsequent centuries. Its ideas were largely accepted by Christian authors--a number of writers and painters, for instance, depicted St. Christopher as a dog-headed man of exotic origin. Pliny’s text and its descendants may have had some influence among Zoroastrian and Muslim writers as well--though these echoes might also reflect independent Perso-Arabic and/or Central Asian traditions of monsters at the global margins.

More contentious than Pliny’s monstrous beings, at least for Christian audiences, were the inhabitants of the Antipodes. Greek and Roman geographers knew the world was spherical, and further divided it into zones--frozen at the poles, unbearably torrid at the equator, and just right in the two “in-between” bands. The known peoples of the world inhabited the northern temperate zone, but who, if anyone, lived in the southern one? In his City of God (c. 426 CE) , St. Augustine--who also commented on the “monstrous races,” noting that the key question was whether or not they were children of Adam, and so worthy of salvation--rejected the idea of an inhabited antipodal region. The Bible had no mention of Adam’s descendants colonizing such a region; besides, in order to do so, they would have had to traverse the hellish equatorial fires. Later commentators also emphasized that the Christian commandment to evangelize all the nations of the Earth would have been impossible, if some of those nations were entirely inaccessible; belief in the Antipodes was thus declared heretical. Still, speculation continued--antipodes could also be interpreted as “feet turned backwards,” and so monstrous races of that description were located in various parts of the globe.

A number of cultures also told stories of fantastical islands in the Atlantic. These tended to emphasize the paradisiacal, blessed nature of these “Fortunate Isles.” Food and drink abounded, disease and old age were unknown, and the inhabitants lived in ease and comfort. The Irish immrama texts are an important corpus of such legends--Navigatio Sancti Brendani (“The Voyage of Saint Brendan,” c. 800) and Immram Brain (“Bran’s Journey,” c. 8th century) are classic examples.

When Europeans did travel to far-off regions, including the Americas, they brought with them this complex of ideas. Combining with their observed impressions, it produced blends of the realistic and fantastic. Thus, in Eiríks saga rauða (The Saga of Erik the Red), written several centuries after the first Norse voyages to North America, some descriptions of the Vínlandic populations--such as their use of skin boats, and unfamiliarity with iron weaponry--may reflect actual observations of Indigenous peoples such as the Beothuk, Innu, and Mi’kmaq. Others--such as the einfætingr, the “one-footer” who fatally shoots Thorvaldr--are straight out of Pliny. Columbus’s descriptions of the Antilles are heavily influenced by the “Fortunate Isles” tradition, even when he’s not describing fetching mermaids in the Caribbean waters. Many locations in the Americas, such as the Amazon River, are named after the unusual beings that Europeans expected to encounter in such regions. Well into the modern era, descriptions of creatures such as Bigfoot, lurking out at the frontier, can trace at least some portion of their genealogy back to Ancient Greek and Roman notions of who lived beyond the borders of their narrowly-defined civilization. And while the extraterrestrials you mention in your question are more often linked to folkloric accounts of fairies and hidden folk (which were themselves sometimes linked to the Antipodes!), the basic axes of otherness that the classical authors delineate--zoomorphic hybridity, modified human bodies, taboo-breaking societies--are all to be found among modern imaginations of alien life.

There’s abundant literature on all these topics. Besides the primary sources mentioned above, John Block Friedman, The Monstrous Races in Medieval Art and Thought (2007); James Robert Enterline, Erikson, Eskimos, and Columbus: Medieval European Knowledge of America (2004); Jerold C. Frankes, “Vikings, Vinland and the Discourse of Eurocentrism,” Journal of English and Germanic Philology 100 (2001); and Fernando Aínsa, “The Invention of America: Imaginary Signs of the Discovery and Construction of Utopia” (1989) are just a few places to begin.