At first glance, this Medrash does not seem to provide a balanced answer, for Bilaam was a most evil person, and he advised his followers to commit all types of misdeeds. Thus, it would appear that the nations did not really get a fair chance, for had they been provided with a prophet such as Moshe Rabbeinu, they would have been led on a path of avodas Hashem. What is the Medrash Tanchuma really telling us?
The answer is simple. Bilaam was a free-agent prophet. Unlike the Jewish nevi'im, he was not a leader. Moav and Midian did not seek Bilaam's objective prophetic advice, nor did they have any intent in becoming his disciples or appointing him as their leader so as to receive nevuah from God so as to lead lives according to His will. Rather, these nations sought to destroy Bnei Yisroel, and they exploited Bilaam's nevuah capabilities to this end. Bilaam, in his hatred for the Jews, was all to happy to cooperate for the right fee.
Thus, the nations were indeed given the opportunity for prophecy, but they voluntarily abused it in the extreme.
The Tanchuma's position still seems to beg the question, for why were the nations not given leaders such as Moshe? Surely such leaders would have inspired pureness of deeds and attitude. Cannot the nations complain that they were unfairly granted leaders of lesser quality than those of Bnei Yisroel? Why did the Tanchuma not consider this point?
The answer is that Jewish manhigim (leaders) are not provided as an out-of-the-blue hand-out. Hashem provides inspiring and holy leaders due to His covenant with us, which was precipitated by a sincere and active commitment to God on the part of the Avos and subsequently the Dor Deah. This is precisely why our classic manhigim were referred to as Ro'im - Shepherds - for they were sent to tend to God's flock, which had a pre-existing covenant based on merit.