Balak son of Tzipor saw everything that Israel did to the Amorites. Moav feared the people [Israel] exceedingly... Moav said to the elders of Midian... And Balak son of Tzipor was king of Moav at that time. (22:2-4)
The structure here seems awkward. First we start off with Balak. Then we suddenly switch to Moav's fears and the attempts to deal with them - not yet knowing the connection between Balak and Moav. And finally we learn that Balak is king of Moav. Wouldn't it have been better to say "Balak son of Tzipor, king of Moav" at the beginning and have everything clear?
Perhaps, the structure is meant to show that "Moav" is independent of Balak. The fear of Israel was not (just) Balak's personal fear, but the fear of his entire country. When "Moav" speaks to the elders of Midian, it most likely means that the elders of Moav are speaking to their Midianite peers. Balak, the king, does not even seem to be present.
The message seems to be that Balak is not such a bad guy; he was not furthering his personal ambitions, but rather responding to his nation's fears. If we had said "Balak king of Moav" at the beginning, we would have thought that "Moav" referred to Balak himself.
Thus, the story may be fundamentally caused by the people's fears and not by any action on Balak's part. Despite this, Balak is introduced briefly on the first line, because after all he is the main character in the story (along with Bilam). But at this stage all he does is "see"; the actual chain of events only begins in the next verse, with his people.
(This explanation is similar to those of Kli Yakar and Rashi.)
God came to Bilam and said to him, "If these men have come to invite you, rise and go with them. But whatever I command you, that you shall do." Bilam arose in the morning, saddled his donkey, and departed with the Moavite dignitaries. But God was angry at his going; so an angel of Hashem placed himself in his way as an adversary. (Bamidbar 22:20-22)
[God to Moshe:] "Say to Pharaoh: 'Thus says Hashem: Israel is my firstborn son. I say to you: let my son go serve Me. If you refuse to let him go, I will kill your firstborn son.' " When Moshe was lodged on the journey, Hashem met him and strove to kill him. Tzipporah took a flint tool and cut her son's foreskin... thus [Hashem] let [Moshe] alone. (Shemot 4:22-26)
I was happy with myself for noticing the parallel between these two stories - especially the shared textual difficulty and what is most likely the same resolution. But it turns out I'm not the first to notice. Come to think of it, I may have read that post at some point in the past and subconsciously remembered it now...
[Bilam] came to [Balak], and he stood by his burnt-offering, and the princes of Moab with him. Balak said to him: "What has Hashem spoken?" (23:17)
It is understandable how Bnei Yisrael believe in Hashem, and also how Bilam believes, since he has received prophecy. But what is the idolatrous Balak doing offering sacrifices to Hashem and relying on His word?
I think the answer is that idolatries are not mutually exclusive. Balak could believe in various Moavite deities, while also accepting the existence of an Israelite deity. In Balak's mind, the Moavite deities would naturally tend to favor Moav, while Hashem would favor Israel. If war broke out between Moav and Israel, it would effectively be a battle between Hashem and the Moavite deities - which could go either way. But if somehow Hashem could be led to reject Israel, then all the deities would be on Moav's side, and its chances would be much better. Balak tried his best to manipulate Hashem, through Bilam, and failed. All was not lost though, because he thought he could still rely on his own deities.
The entire Balak story is notable because of its almost total lack of consequences. Israel never hears about the attempted cursing. Bilam goes home and resumes life as normal (though Balak will soon recall him for a slightly different task). Balak abandons magical incantations and turns to more practical ways of making God angry at Israel. And Moav is not invaded even after the Baal Peor episode, so in retrospect Balak's fears were baseless.
It seems that the only "value" of the long Balak story is as a theological statement - that God is transcendent, that He cannot be manipulated by humans but rather determines their personal and national destiny, and that His relationship with the Jewish people is permanent and will not be altered on a whim.