First some things that I expect we can all agree on. There are a LOT of ingredients that go into human speech, and they probably didn't all evolve at the same time. There is a continuum of traits, presumably of different cognitive complexity and different stages of evolution. On one end we have the most basic things, like forming sounds and the cadence of speech. Then there is vocabulary - learned combinations of sounds that have specific meanings. Moving on we have morphology, like how to pluralize words, and some simple rules for combining them. "Me Tarzan, you Jane" is basically a proto-language, that would have been good enough for most hunter-gatherer needs. Only at the highest levels of complexity do we see things like subordinate clauses and recursion. Humans are the only living creatures that are known to have made any progress along this continuum, but there must be a "missing link" between what we have and animal sounds.
So the question "did Neanderthals have language" is an oversimplification. It's not a binary answer; you can have vocabulary without recursion. The real question is where Neaderthals were on the language continuum. Could they have written Shakespeare? Did they top out at "me Tarzan, you Jane"? Were there any words at all? The "old guard" school of thought in linguistics (to which I mostly subscribe) is that they had a proto-language, but none of the more complicated structures like recursion. Other researchers have argued that their culture and very-close-to-human biology suggests that they had the whole deal. There is nothing on the horizon that could really settle this question, but it's an interesting one to pose.