Why did Moshe build a Mizbe'ach?
Ha'amek Davar: To thank Hashem for the good news that He would erase the name of Amalek. 1
Presumably, he brought Korbanos on it, as Targum Onkelos intimates.
What exactly, did he call 'Hashem Nisi'?
Rashi and Ramban: Refer to Bereishis 33:20:1:1**.
Seforno: He called the name of Hakadosh-Baruch-Hu in prayer; 1 'Hashem shall be my champion' against all those who rise against me. He called the Mizbe'ach 'Hashem is my flag-pole' 2 - because Hashem's staff served as a flag-pole on the hill (to rally the army to fight against Amalek). 3
Targum Yonasan: He called the name of the Mizbe'ach 'the word of Hashem, that the miracle that Hashem performed when His Shechinah passed here was for my sake'. 4
As in Tehilim (60:6) "Nasata li'Yere'eicha Neis Lehisnoses" (Seforno). And in the same way, Hashem will raise His staff on the mountains, to call the armies to fight against Amalek, as He told Moshe "Ki Machoh Emcheh ... " (Rashbam). In similar fashion, it is customary to call people after miracles that occurred or that are destined to occur (as for example 'Eliezer' (Shemos 18:4) and 'Imanu Keil' (Yeshayah, 7:14 [Rashbam]). Refer also to Bereishis 33:20:1:1**.
See also Ba'al ha'Turim.
Since Yisrael were not worthy of miracles at that stage (See Na'ar Yonasan).