Jean Auel's The Clan of the Cave Bear book-series explores the possibilities of Neanderthal/Cro-Magnon interaction, but this article brings up a whole new set of intriguing plot twists.
So far, there are two proven gene-flow events to Homo sapiens from non-sapiens: Homo neanderthalensis and from the Denisova hominin population. In the latter case science isn't sure yet whether the Denisova hominin was a sub-species or species.
We probably got some immunity-related genes from neanderthals, but probably not red hair - red hair in neanderthals is caused by a different mutation that doesn't exist in humans.
