First the discoveries, then some alternate history speculation:
Island discoveries. Early humans managed to reach a few large islands that are isolated from the mainland even during ice ages. When they got there, they were isolated enough to develop into very different ways of being human.
1) SulawesI: Most recently: Stone tools dating back to 115,000 years were found on the Indonesian island of Sulawesi. No human remains were found with the tools, but the tools are far older than the time when modern humans arrived in the area. Sulawesi hasn't been connected to the Asian mainland at any point where there were humans on the planet, so there is a very good chance that whatever humans managed to reach there were isolated for a prolonged period and developed into a very odd island form like the Hobbits in Flores. (http://phys.org/news/2016-01-stone-a
2) Flores Hobbits: As most people know, fossils of tiny, very primitive humans were discovered in Flores (also in Indonesia) a few years ago. A noisy minority of scientists claim that the fossils are of modern humans with a genetic disorder, but the early date of some of the bones and the fact that stone tools dating back 800,000 years in Flores point to primitive humans having arrived there and survived almost until the first development of agriculture--until maybe 18,000 years ago.
3) Early man on Meditteranean islands: Ancient human remains and tools have been found on some of these islands, including Cyprus and Crete. There is some evidence that pre-modern humans reached Sardinia, off the coast of Italy, but no remains have been found.
'Fossil' DNA discoveries:
1) Neanderthal/Human interbreeding. Neanderthals were a species or subspecies of humans who branched off from the line that led to modern humans around five or six hundred thousand years ago. That means that genetically they were around eight to ten times as different from modern humans as any of us are from one another. At first, the genetic evidence seemed to say that modern humans and Neanderthals didn't interbreed, but more detailed genetic studies seem to indicate that about one to four percent of the genetic material from modern Europeans and Asian (but not Africans) is from Neanderthals, with most of those genes related to the immune system. There is some evidence of reduced fertility between the Neanderthals and modern humans, but the some fertile offspring were obviously possible.
2) Denosovians: A few years ago, scientists extracted DNA from a human finger bone found in Siberia. They discovered that the DNA was from a population of humans at least as different from us as the Neanderthals, though without more skeletons they don't know how these people differed from us. We have found pre-modern human skeletons in China and Java, and it would be logical to tie them to the Denosovians, but there is no proof yet that they are from the same group. Whoever the Denosovians were, they interbred with modern humans and provide single digit percentages of the ancestry for some groups in Asia, New Guinea and Australia. Possibly related, though the link is unproven: pre-modern humans (the "Red Deer People") seem to have survived in tropical southwestern China until around 14,000 years ago, with possible hybrid populations surviving a few thousand years after that. It's possible, but unproven, that these were the last relatively pure descendants of the Denosovians. Making matter more complicated, there is some genetic evidence that the Denosovians interbred with yet another unknown group of humans.
3) Pre-modern human population in southeastern Africa: This was a very strange discovery. An African-American man submitted a DNA sample to one of the "Find Your Ancestry" type places. They did the standard checks, looked at the results and said, "Say what?" They bumped the results up to higher level people, who discovered that the guy's "Y" chromosome was from a lineage that branched off from the rest of humanity about the same time the Neanderthals did. The rest of the guy's DNA was reasonably normal. They did some tracking and discovered a small cluster of men with similar Y chromosomes in Cameroon. Implication: A population in that area may have branched off several hundred thousand years ago, then been genetically swamped by modern humans, contributing an unknown percentage of their genes to local humans. Unfortunately, DNA is unlikely to be preserved in tropical Africa, so it'll be difficult to figure out which genes and what percentage whis group contributed. The fact that a Y chromosome lineage survived may mean a slightly higher percentage than Neanderthals or Denosovians contributed, but that's totally speculation.
Bottom line: As of fifty thousand years ago, our ancestors shared the planet with at least four and probably six or more populations that were close to ten times as different from modern humans as any of us are from one another. Were they separate human species? By the standard textbook definition, that separate species can't interbreed, apparently not, at least in the case of the Neanderthals and Denosovians. On the other hand, a lot of species that most people acknowledge a separate can interbreed-coyotes with wolves and polar bears with brown bears for example. If species split, it logically should at times be a gradual thing, where interbreeding may be physically possible and still produces fertile offspring for a while, but the ecology and behaviors of the populations make interbreeding rare enough that the genetics of the two populations are distinct and eventually diverge enough that they can't interbreed.
Lets get to the alternate history already! There are couple ways we can go with this: First, we can speculate on what might have happened if primitive humans had survived somewhere in the Old World long enough to be discovered and maybe enslaved by Old World civilizations. That's the alternate history idea behind my novel All Timelines Lead to Rome. A primitive hobbit-like species of humans survives in Sardinia long enough to be enslaved by the Neolithic humans who colonized Sardinia. Rome eventually finds and makes use of the primitives, making them a cross between slaves and pets and remodeling their empire around the primitives to the point where it is Rome in name and superficial structure only. If you think about it long, you'll realize that there is a bit of hand-waving going on to get a recognizable Roman empire in a world where primitive humans have been around in the Meditteranean for over seven thousand years where they didn't survive historically.
You could, of course, have the primitive island humans surviving anywhere along the fringes of the continental shelf of the Old World and have them preserved in some isolated area until modern times. If something like the Flores hobbits had survived long enough I could see Chinese emperors preserving a population in some royal reserve like they did some species of deer. The best possibilities for survival would have probably been New Guinea or the Phillipines, though there is no evidence that primitive humans every reached either place. Another possibility: something like the Red Deer people survives in China long enough to be enslaved. The problem with all of these scenarios is that wave after wave of our kind of humans has swept across every human-inhabitable part of the Old World and many lines of our one kind have been swept into oblivion. It's unlikely that little pockets of these very different humans could have survived that process, at least in or near the Old World. So we resort to hand waving.
But what about other human species as serious competitors all the way to the present or at least until Europeans or someone else swept across the world and created a world economy? That would probably take one of the other types of humans getting to the New World and/or Australia. That wouldn't have been impossible.
Australia would be the easier of the two. A couple strings of islands stretch from Asia to Australia, or to New Guinea, which is attached to Australia during ice ages. If the Denosovians stretched as far south as southeast Asia, they could have island-hopped to Australia, maybe as early half a million years ago. If the ancestors of the Flores Hobbits were really in Flores 800,000 years ago, they could have kept island-hopping until they New Guinea and then walked across a land-bridge to Australia. At that point, their survival would depend on being able to stop further colonizations from the mainland, first from mainland versions of their own kind, then from waves of modern humans. It's interesting to think about the equivalent of Captain Cook stumbling across an Australia and New Guinea with surviving pre-modern humans as opposed to the historical inhabitants. It might even be possible to fit in both a hobbit-like species in the less accessible rainforest parts of New Guinea and Denosovians in the bulk of Australia, though that might be pushing it a little.
Denosovians would also be the logical kind of humans to beat us to the New World. Harry Turtledove explored those possibilities in a series of short stories and novellas collected together as A Different Flesh, but the pre-moderns he described would have had a very difficult time reaching North America. The problem: There are only a few ways to get to the New World from Asia (1) Over a land bridge that only appears during ice ages, (2) By boat over cold, treacherous water or (3) Walking across frozen ocean during an Arctic winter. The land bridge option and the walking across ice options only work if you can first get across a large stretch of Siberia during an ice age. Siberia was one of the last places in the Old World that early modern humans were able to inhabit, simply because of the harsh climate.
The best bet for Denosovians would have been to make it by boat in the last interglacial--a period roughly 125,000 years ago when average temperatures were a degree or two warmer than they are now for a geologically brief period at the peak of the warming. There were other, earlier interglacials, but the later ones gave the best chance for them to have developed the technology to get across the Bering Strait. That's unfortunate, because the earlier the better in terms of developing an interesting environment for stories. Half a million years in the New World could yield not one but several species of humans, with some adapted to temperate forests, others to the plains and mountains and the jungles of South America, plus maybe yet more island species in the West Indies. Of course these people would then have to keep the continent from being taken over by PaleoIndians when they arrived, which wouldn't be easy, though they would have a disease gradient going for them--they would have had time to be parasitized by a lot of New World diseases the early Indians wouldn't be immune to and the Indians wouldn't have a comparable set of diseases to spread in return--hunter-gathering in the arctic in small bands doesn't give much margin for sick people to survive long enough for diseases to sustain themselves long-term.
But what about the Neanderthals? I wrote a scenario where Neanderthals made it to North America. That's probably a stretch. If the Denosovians inhabitabited most of eastern Asia, Neanderthals would have to get past them to get to the Bering Strait. Not easy. They might travel by boat along the fringes of the ice sheets in the North Atlantic during an ice age, but that would be tough at their level of technology.
So what do you think? Finding people far more different than us than Indians when we arrived in the New World. Europeans debated whether Indians had souls. The questioning would be a lot tougher if they met humans from a different species. There would be a genuine question as to whether the inhabitants should be considered men or beasts.