The part of the Neanderthal genome tested so far is 99.5% similar to the genome of a modern human. This is far from being "completely different" considering that the lowest similarity between two modern humans appears at present to be 99.7%.
The variety of Neanderthal sequenced is one of the southern European subspecies. It is still unknown how much genetic diversity there was between various subspecies of Neanderthals, but judging from the 600,000 years of evolution and the clear physical differences between the 3 main subspecies (bigger differences than between modern humans), it is probable that Neanderthals had a higher genetic diversity than modern humans. Furthermore, if modern humans interbred with Neanderthals, it would make sense that this happened in Central Asia, where red hair and other features shared with Neanderthals first appeared. There is no genetic data from Central Asian Neanderthal yet.