Yes that is correct. The deification (I learned a new word!) of Jesus is the biggest reason why Muslims dislike Christianity, and they dislike Judaism for not having accepted Jesus as a prophet.
I think they are more concerned with the Christian belief in Jesus' crucifixion, which they consider to be unworthy of a prophet. Muslims don't believe that Jesus was crucified at all, which is a bit of a problem since that's pretty much the one thing we can be sure of about him.
Maybe. But Paul is the earliest Christian writer we have, and he definitely had some notion of the Incarnation (Philippians 2:5-7, off the top of my head. Colossians 1 also has a lot of material to that effect). But then that's not 100% clear from later parts of the New Testament. So perhaps it'd be more accurate to say that there was a time when some Christians did not believe Jesus is God. And as Eran noted, that's effectively how things are today.
The degree to which the first Christians did or did not believe that Jesus is God is still fairly hotly disputed in New Testament studies. Certainly Paul seems to have held what was in some respects a "high" christology involving the pre-existence of Jesus - although that's not quite the same thing as regarding him as God. (And the authorship of Colossians is disputed, so it's not safe to take that as evidence for his views, at least.) I agree though that it would be unsafe to assert that there was a time when Christians in general did not believe Jesus to be God. Certainly there have always been
some Christians who didn't, but that's not the same thing.
Even if it says christians and Jews are people of the book, this just means that they are people who follow a holy book. That's not to say that the Koran teaches to like those faiths, it most certainly does not teach much tolerance towards non Muslims.
I think it does, but I'm no expert on the Koran.
I've been told by several Muslims that they think that the Christian Trinity is God, Jesus and Mary. To be fair, this makes at least as much sense as the Christian version, and in practice (at least in the Catholic church) there doesn't seem to be much difference between 'veneration' of the Virgin and 'worship' of her. It's also much easier to make a statue of Mary than of the Holy Spirit.
Yes, I understand that this is a common misconception among Muslims.
What is the Holy Spirit, anyway? Can 'the breath of God' or 'the word of God' be separate from God? To what theological need or question is 'the Holy Spirit' a good or necessary answer?
The "word of God" is not the Holy Spirit but the Son, the Logos. Neither is "separate" from God. According to orthodox Trinitarianism, the Father, the Son, and the Holy Spirit are all equally the one God. They are distinct from each other but not separate from each other.
Christian orthodoxy has two answers to your main question. The first is that the Holy Spirit is God active among his people. It is, for example, the Holy Spirit who infuses grace into believers, who acts upon them to bring them into union with God, and so on. It is, moreover, the Holy Spirit who speaks by the prophets. The second answer is that the Holy Spirit is the principle of love within the Godhead. Just as the Son is the rationality of God, including his self-knowledge, the Spirit is the love of God, including his self-love. This basic position goes back to Augustine and was also interestingly developed by Jonathan Edwards. Edwards argued that there
must be a Trinity if God is omniscient, because his omniscience means that he has a perfect idea of himself. But if this idea is perfect (as it must be) then it is itself a divine person, namely the Son. And if the Father loves the Son (as, again, he must), this love itself is a further hypostasis, namely the Spirit. Each Person knows with the Son and loves with the Spirit, making them a single God.
There's another argument for the Trinity, which rests on a rather different view of the functions of the Persons, that was developed by Richard of St Victor and revived by Richard Swinburne. The argument is that if God is essentially loving, this love must necessarily be productive. So there must be at least two Persons of God, because the Father, to be truly loving, must necessarily beget the Son. (The creation of the universe isn't enough to fulfil this necessity, because creation is contingent - otherwise it would be co-eternal and co-necessary with God.) And furthermore, true love of another is itself necessarily productive, which means that the perfect mutual love of Father and Son must generate a third Person, the Holy Spirit. I find this argument less convincing than Edwards', which itself is somewhat dubious, even when expressed far less sketchily than I just did.