What does the Pasuk mean when it states that Bil'am saw Amalek?
Rashi and Ramban #1 (citing Rashi): It means that he saw the punishment (the downfall) of Amalek.
Ramban #2, Rashbam and Targum Onkelos: It means that he actually saw Amalek from the vantage point where he was standing. 1
Why does he refer to them as "Reishis Goyim"?
Rashi, Ramban #1 (citing Rashi), Rashbam,Targum Onkelos and Targum Yonasan: Because they were the first to attack Yisrael 1 (after they became a nation).
Ramban: Because they were a leading power among the nations. 2