"And now, write down for yourselves this song, and teach it to the Children of Israel..." (Devarim 31:19)
The Torah calls Haazinu a song. But it seems to be anything but a song. It is full of negative predictions and severe warnings. "Yeshurun waxed fat, and kicked... and forsook the G-d who made him... And Hashem saw and He was offended, and He said, I will hide My face from them... I will persecute them with a people that is not a people, with an immoral nation I will anger them, for fire burns in My nostrils..." Finally, Haazinu predicts the punishment of Israel's enemies, who, seemingly, were merely instruments to execute G-d's justice: "For He will avenge the blood of His servants." How are the Jewish people His servants if they sinned so grievously against Him? Is this racism?
We can answer this based on the Rambam (Hilchos Teshuva 5:10) who poses the famous problem of the contradiction between free will and G-d's foreknowledge. The Rambam hints at the answer, but says that the full answer to this question is beyond human comprehension. The Raavad gives an answer. Both agree, however, that there is no contradiction and G-d's knowledge does not prevent us from having free will.
Later (Hilchos Teshuva 6:11), the Rambam asks how there can be free will after the Torah records prophecies that the Jews will one day sin. He answers that the Torah does not specify who should sin, and therefore every Jew has to make sure not to be the one. We see that the Rambam holds that when G-d reveals His foreknowledge to mankind, there is no longer free will. The only way out is if the prophecy is unspecific. (The Raavad disagrees with this and holds that even when G-d reveals His foreknowledge, there is still free will.)
According to the Rambam, the existence of predictions in Haazinu about the Jewish people sinning means that the nation as a whole has no choice but to sin. Individual who sin will be punished, but a certain percentage of the people must sin in order to fulfill G-d's decree. Therefore their sin is not a negative thing. It is part of G-d's plan to bring about the exile, whose purpose is to add converts to the Jewish people and bring the light of the Torah to all corners of the world. Moreover, although each individual has a choice whether or not to be one of the sinners, those who choose to sin are performing an act of self-sacrifice - subjecting themselves to punishment so that G-d's plan might be fulfilled.
With this, we can understand why certain other great people sinned. King David was perfectly righteous and beloved to G-d. The Midrash (Bereishis Rabbah 29:3) says that there are three "finds" that G-d found in this world: Abraham ("and You found his heart faithful before You" - Nechemiah 9:8), King David ("I have found My servant David" - Tehillim 89:21) and Israel ("like grapes in the wilderness I have found Israel" - Hoshea 9:10). How can this be if David sinned in the episode of Bath-Sheba? Moreover, our Sages say that four people went their entire lives without sinning: Binyamin, Amram, Yishai and Kilav. Yet it does not say that any of these people were G-d's special "find". They were not as great as Moshe and David, who did sin.
The answer is that Moshe and David sinned in order to fulfill G-d's plan. Moshe knew that he was destined not to bring the Jewish people into the Promised Land, so he committed a sin to make that punishment justified. David wished to teach repentant sinners how to repent (Avodah Zarah 4b-5a), so he committed a sin. Furthermore, he did it so that he should not win his debate with G-d over whether he was capable of standing up to the test: "To You alone I have sinned, and I have done what is evil in Your eyes, so that You should be correct in Your words" (Tehillim 51:6). "David said before the Holy One, blessed is He: It is known to You that had I wished, I could have controlled my inclination, but I did not want people to say, a servant defeated his Master."
Moshe and David knew that it was the will of G-d that these things should happen. So they undertook to sin with self-sacrifice, knowing that they would be punished.
The Gemara (Sanhedrin 102a) says that Yeravam, the first king of the Ten Tribes who introduced idol worship, was told by G-d when he first began to sin, "Give up your sinful plan, and you and I and [King David] the son of Yishai will walk together in the Garden of Eden." Yeravam asked: "Who will walk in front?" G-d answered, "The son of Yishai will walk in front." "If so," said Yeravam, "I do not want it." Now, Yeravam was not a simple man. The Gemara says earlier on that same page, based on the words "and the two of them were alone in the field" (Melachim I 11:29), that Yeravam and Achiya were so great that all the other sages were like grass of the field to them. So how could he have spoken so brazenly to G-d, and how could he have refused to repent just because he would be less righteous than David? The answer is that Yeravam understood it was G-d's plan that he should be lesser than David. He therefore decided to sin deliberately so that G-d's plan would be fulfilled.
We see the same concept of a sin committed in order to fulfill G-d's will in the case of the earth during the creation of the world. When G-d created the trees, He said, "Each tree of fruit making fruit" (Bereishis 1:11) meaning that the wood of the tree should taste the same as its fruit. But the earth disobeyed this order (v. 12). Its punishment was that it was cursed along with Adam after Adam ate from the Tree of Knowledge. Yet the earth, in its sin, was actually fulfilling G-d's will, as we see in Midrash (Bereishis Rabbah 12:16): "On the day that Hashem G-d created earth and heaven - this is comparable to the legion that accepted the king first. Said the king: I will give it a special gift of honor that it can never lose. Here too, said the Holy One, blessed is He: since the earth was the first to carry out My plan, I will give it a gift that it can never lose, as it says, He founded the earth on its foundations, so that it should never move, forever and ever. "
Here too, Haazinu means "listen." The message of Haazinu is: Listen, the Jewish people did not rebel against G-d. They sinned deliberately so that G-d's plan of exile could be fulfilled. "Praise, O nations, His people, for He will avenge the blood of His servants." When the nations see that the Jewish people, out of love for G-d, committed sins and accepted their punishment in order to fulfill G-d's plan, they will see that the Jews truly deserve to be called G-d's servants, and they will praise them.