Pygmies and Khoisan have admixture from a distinct population at the level of ~2%. This population diverged from the other ~98% of their ancestry ~700,000 years before the present, and the hybridization occurred ~30-40,000 years before the present. Most other African groups have only traces of this element, with some West Africans lacking it. . . . Mbuti Pygmies of the eastern Congo likely have a special place in this possible admixture event. In particular, they seem to possess the diverged variants found in the western Pygmies, the Biaka, and the Khoisan populations of southern Africa. As assumed the pattern of admixture seems to be such that the two Pygmy groups and the Khoisan exhibit elevated signatures of archaic contributions, while other African groups manifest admixture in direct proportion to their known admixture to the aforementioned populations. For example, the Bantu group with the highest proportion of admixture are the Xhosa, who also have the most Khoisan ancestry of non-Khoisan populations. The West African Mandenka seem to have trivial admixture from this archaic group.
The African outgroups with the highest levels of archaic admixture (whose absolute numbers are small, perhaps in the hundreds of thousands, and are a very small proportion of all Africans, perhaps 0.1% of all Africans) became distinct populations of modern humans around the time of the main Out of Africa event or perhaps a couple tens of thousands of years earlier.
The lowest levels of ancient admixture appear to be populations where Y-DNA haplogroup E and mtDNA haplogroups L2 and L3 are most common, a group that includes the African contribution to almost all African Americans in the United States.
This adds to the recent discoveries based on comparisons with ancient DNA that Melanesians and people from populations with some Melanesian ancestry seem to have significant levels of admixture with a population known genetically today called the Denisovians who left genetic traces in Southern Siberia, and that all Eurasians have a small but significant proportion Neanderthal ancestry, with immune system genes seeming to have an outsized contribution and the European and Asian inheritances from Neanderthals being mostly disjoint.
The Denisovian admixture presumably took place close in time to the modern human settlement of Melanesia, around 45,000 to 50,000 years ago. Denisovians aren't clearly identified with a particular species of archaic hominins, although Neanderthals, late stage Homo Erectus and "Hobbits", or some hybrid of these, are the main potential contenders in the relevant time frame. The number of people with significant Denisovian admixture today probably numbers in the tens of millions or perhaps the low hundreds of millions.
Neanderthals went extinct around 30,000 years ago, but a very large share of European ancestry dates to sometime after the Last Glacial Maximum ca. 20,000 years ago, after which Europe was repopulated from outside Europe and from a few refugia in Southern Europe. Thus, even if Upper Paleolithic modern humans in Europe (the Cro-Magnons) had elevated levels of Neanderthal admixture, they may have been mostly replaced or diluted beyond recognition by subsequent population waves in much of Europe.
The fact that both modern Asians and modern Europeans have similar levels of Neanderthal admixture, but that their Neanderthal legacies don't overlap much, suggests that Neanderthal admixture probably happened mostly in or near the Near East not long after the Out of Africa event, or possibly even during a "false start" Out of Africa event ca. 100,000 to 75,000 years ago that mostly fizzled with the first wave either dying out or retreating to refugia either in Africa (probably in the Northeast if there) or outside of Africa (Arabia and South Asia are strong possibilities) until a more successful Out of Africa event ca. 50,000 years ago that started the colonization of Europe.
Best guesses of the period of archaic hominin and modern human interaction in any one place are on the order of 1,000 to 2,000 years where estimates are possible, but the expanding frontiers of modern humans meant that someone, somewhere there were archaic hominin/modern human interactions for tens of thousands of years in modern human history. The Hobbits of Flores are the last documented archaic hominins to persist, perishing ca. 18,000 years ago. But, archaic hominins were extinct everywhere long before agriculture, stable decent sized towns, domesticated animals other than dogs, or other hallmarks of modern society arose. Indeed, at the time of archaic admixture modern human racial divisions were just starting to emerge.
The first farmers in the Danube and the hunter-gatherers that they displaced, numerically overwhelmed and absorbed, or caused the death of (either directly or due to resource conflicts) would have been as different in appearance as an Australian aborigine and a typical citizen of France. Immense human genetic diversity from the hunter-gatherer era across the world was wiped out as farming populations expanded. Their overlap as co-existing populations was also probably on the order of a thousand years in any one place.
Neanderthals flourished after the hominin species such as Homo Erectus who are likely sources of archaic admixture with Africans became distinct and before modern humans.
There are no Y-DNA or mtDNA contributions to archaic hominins in anyone. No one on Earth has an ultimate matriline ancestor or patriline ancestor who is an archaic human who lived after the common ancestors of all modern humans.
Biblical references to admixtures of humans with "giants" and angels (one of which is quoted by Razib in his post) seem unlikely to derive from these ancient admixture events that would have taken place not less than 26,000 years before writing was invented and probably 20,000 years before any of the major language families in the world today existed, leaving hundreds of generations across many, many languages that oral histories would have to survive though in a society that wandered the Earth in small bands in which people had average life expectencies on the order of 40 years or less. Goliath, for example, was probably a Mycenian Greek relocated to the Levant following the Bronze Age collapse, if there is any historical basis to that story.