Hominin diversity

I found this article from Natural History Magazine via the Anthropology in the News website from Texas A&M Univeristy (my undergrad alma mater). It deals with reconstructing faces of the human past. It struck me how diffferent and diverse hominins were and how this much diversity happened only within the 3-4 million years.
The paper discusses how they reconstruct the faces from the existing bone structure of the skull. Seeing the diversity of faces makes me think of whether in our EEA (environment of evolutionary adaptedness) we often encountered members of different hominin species. The article mentions that there is some evidence of this. A common argument used be evolutionary psychologists against studying ethnicity/race as an evolutionary based mechanism is that the presence of different forms of humans would have been a novel experience for us now in the modern world. Before we never would have experienced phenotypically different humans. I have seen it suggested in this article and elsewhere that this is a possibility.
Check out a post from a few months ago about a paper that disputes this possibility.
Looking at these pictures also highlights to me the fact that the path to modern humans was a well worn one- with respect to different diets, physiology, social systems ... all as recently as 30,000 years ago, with Neanderthals.