"Why did the Holy One rest his Divine Presence upon a wicked gentile? So that the nations of the world should not have an excuse [as to why they didn't serve God]. They would have said, 'If we had prophets, we too would have repented.' So God established prophets for them."
To me this wouldn't seem 'fair'. If the gentiles would want a prophet to help them 'repent' why not establish for them a righteous gentile prophet?
I don't have a source for this, but I always assumed the idea was not Bilaams personal performance, but rather how the nations interacted with Bilaam. "I gave you a prophet and you asked him to help win wars and deliver curses. Couldn't you have asked him for some directions on how to live a meaningful life?" G-d's response to the unasked question is don't tell me that a prophet will fix you, because look what you think a prophet is for.
Being righteous or not, is up to the individual person. G-d can give a person (i.e. Bilam) the gift of prophecy, but then it is up to him how he uses these gifts. Itro is an example of a gentile that searched very hard, and found the truth. When a person chooses a certain path, and has a strong will to go in that path, he/she get help and assistance to go on that path.
Rav Chaim Kanievsky is recorded as having asked this question and answered that Bilam was righteous before he was given nevuah and then became a rasha afterward (because of the power the nevuah gave him, i.e. gaavah, kavod etc.) I will try and find the source for this.
Posibly because when Rashi says 'wicked gentile' he isn't referring to the fact that Bilam himself was evil, but rather to the fact that most gentiles at that point were immoral, in which case one could argue that Bilam was no more evil than the rest of them.
In a similar vein, you could say that Bilam, in order to have had prophecy in the first place, was probably more moral than other non-Jews of the time.