Why aren't we allowed to charge a Jew interest but we're allowed to charge a non-Jew?
A couple of answers that I've seen:
Charging interest is something quite normal in the business world; there's nothing immoral about it per se. However, you wouldn't charge interest on a loan to your brother or sister, because you relate to them as family rather than as business associates. The Torah expects us to treat every Jew like a sibling (which, spiritually, all Jews are - see Tanya, ch. 32). By contrast, our relationships with non-Jews can be businesslike, so long as we treat them fairly (in keeping with their dignity as human beings). (Ramban's commentary to Deut. 23:20)
It's a matter of reciprocity. A non-Jew is allowed to charge a Jew interest, so it is only fair that a Jew should be able to do the same to the non-Jew. (Malbim's commentary, ibid.)
It seems to me that halakhah accommodates the reality that there is a time value of money (opportunity cost and whatnot). Therefore there is no moral problem with charging interest in-and-of-itself. Which is why one may charge interest of a non-Jew. That includes idol worshipers and most monotheists.
Charging and paying interest is only prohibited when both parties are either Jews or geirei toshav. (Resident aliens of a halachic state in Israel who agree to be good citizens and to observe the Noachide laws.)
When your brother needs a loan, demanding they cover your opportunity cost is wrong because it's unbrotherly.
I suggest this based on a literal read of the source verse. Vayiqra 25:35-36:
וְכִי יָמוּךְ אָחִיךָ וּמָטָה יָדוֹ עִמָּךְ וְהֶחֱזַקְתָּ בּוֹ גֵּר וְתוֹשָׁב וָחַי עִמָּךְ. אַל תִּקַּח מֵאִתּוֹ נֶשֶׁךְ וְתַרְבִּית וְיָרֵאתָ מֵאֱ-לֹהֶיךָ וְחֵי אָחִיךָ עִמָּךְ.
If your brother becomes poor and his hand falls with you [i.e. he becomes dependent on you], then you shall uphold him, [even] a proselyte or resident alien; and he shall live with you. You shall not take interest or increase from him, and you shall revere your G-d; and your brother shall live with you.
Notice the brotherhood of all Jews and geiri toshav is mentioned twice in the description of this prohibition. Seems to be the motivator.
The same conclusion is implied by the inclusion of the prohibition in Yoreh Dei'ah rather than among the volume where most fiscal laws appear, Choshen Mishpat. Similarly, in his Guide for the Perplexed (3:35), when the Rambam divides the laws by function, he categories the prohibition against usary as a form of charity:
The fourth class includes precepts relating to charity, loans, gifts, and the like, e.g., the rules respecting "valuations," (scil., of things devoted to sacred purposes, Lev. 27:1-27); "things devoted" (ibid. v 28); laws concerning loans and servants, and all the laws enumerated in the section Zera'im, except the rules of "mixtures" and "the fruit of trees in the first three years." The object of these precepts is clear; their benefit concerns an people by turns; for he who is rich to-day may one day be poor -- either he himself or his descendants; and he who is now poor, he himself or his son may be rich tomorrow.
N.B. not part of the answer, but important to know... The gemara (Makkos 24) explains Kind David (Tehillim 15:1) as praising someone who won't charge interest to non-Jews either. Rashi (ad loc) appears to say this is because it will corrupt the person until they end up charging interest of Jews too. (As he uses the word "nimshach", which usually refers to being "drawn after" sin, rather than habit or mistake.)
Sefer Hachinuch Mitzva 68 says that paying interest causes one to become extremely poor without realizing it until it is too late.
In Mitzva 573 he says that it is inappropriate to do Chesed with those that do not serve Hashem.
Perhaps there is a time value of money when dealing with non-Jews but not when dealing with Jews. Time value of money assumes a certain unchanging nature of money; when dealing with non-Jews who live in nature this is something to reckon with. With Jews, as the Medrash says Hashem told Avraham "go out of your astrology," they are controlled solely by Hashem and are thus beyond nature. Between Jews, time value of money is simply a lack of faith.
See Radak on Tehillim 15:5. He says that interest is not stealing because it is agreed to by both parties. However, a Jew must to kindness to another Jew and lend him without interest. Since most non-Jews hate us, we're not obligated to do them a kindness like that.
He concludes that certainly if the non-Jew does us a kindness, we must do him one in return and lend to him interest free.
(Note the similarity to Alex's first answer).