I see a lot of Halachic and Aggadic texts where the words גוי, נכרי, עכו"ם are all used interchangeably. Usually I notice it in places where two people are using different versions of a text (one from a newer publication, one an older version), and one version has one word, and the other version the other word. Is one of these words considered more politically correct than the other? More modern? Less modern? What's the deal with the substitutions?
The substitutions come from censorship of printing over the years. Christian censors were generally more comfortable with עכו"ם - meaning worshiper of stars and constellations, as those Christian censors felt it did not include them.
It is not really known in many cases what the original term of the text was due to this censorship, but now that we no longer live under such rules, some are recovered from what of the original manuscripts remain or otherwise changed to what the printer regards as "changing back" to undo the censorship.
I'll answer a piece of your question in terms of literal definition as well as "historical" usage:
"Goy" means "nation" and Jews are referred to as a "goy" in numerous places in the Torah. This week's parsha, perhaps, represents the 1st such "usage" in Breishit 12:2, "An I shall make you into a great nation" (Heb. - "Goy Gadol").
"Nachri" means "stranger" - usually, referring to non-residents of the current land. In most cases in Tana"ch, the term is used to refer to non-Jews, but, I think that there are a few places where Jews are called "nachri" when they have been in foreign lands. Offhand, I can't think of an example, but I think there are one or two in Sefer Breishit.
"Akum" is an abbreviation that developed in the time of the Mishnah, I believe, and clearly refers to non-Jews.
When I was learning Masechet Avodah Zarah with my rav, he was careful to differentiate between "akum" and "Nachri" in terms of referring to non-Jewish Americans. He said that every "akum" is a "nachri", but not every "nachri" is an "akum". The discussion arose as to whether Christianity is Avodah Zarah, and there are different opinions. According to those abiding by the ruling that it is, a devout Christian would be "Akum". But, as not every non-Jew practices any religion (there are many American atheists, e.g.), these would be considered "nochrim" but not "akum".
"Goy", for some reason, received a derogatory connotation, but I don't quite understand why, when, or how.