What is the meaning of "Nora'os b'Tzedek Ta'anenu"?
Rashi: Answer us with Your Tzedakah, to do awesome acts to the nations.
Radak: Answer us with Your Tzedakah, to do awesome acts with us, for You are Elokei Yish'enu. Miracles above nature are called Nora'os, for they make Hashem awesome over people.
Malbim #1: You gave to us an awesome answer - the famine was "El Sha'ul... Asher Hemis Es ha'Giv'onim" (Shmuel II, 21:1)
Malbim #2: Descendants of Sha'ul were killed [to appease the Giv'onim]. This made everyone fear!
What is "Mivtach Kol Katzvei Aretz"?
Rashi: [You are] a refuge in which all land dwellers, from one end of the land to the other, can rely on.
Radak: [You are] the reliance of all Yisrael scatted to the ends of the land and of the sea, far from Yerushalayim. "Katzvei" applies also to the sea, i.e. islands. Also "mi'Tzafon umi'Yam" (107:3) refers to islands. "Umi'Yam" does not mean the west, for the verse already said "umi'Ma'arav"!
Malbim: The reliance of the entire world depends on Tzedek. If they do Tzedek Bein Adam l'Chavero, they will have security. This hints to their injustice to the Giv'onim, and they found favor with Hashem via appeasing the [Giv'oni] converts.
Why does it say "v'Yam Rechokim"?
Rashi: Also for people far on the sea, You are a reliance, for Your authority is everywhere.