To the best of my knowledge eating fish after meat has the same Halacha as eating meat after fish. You are supposed to eat a cracker and take a drink to separate between them. Why is it most common for people to eat fish at the Shabbos Seuda first and then meat - from the Zemiros the order is "Basar V'Dagim V'Chol Matamim" - should we not eat the meat first and then the fish?
There is a Kabbalistic idea that fish (which live in the water, representing עלמא דאתכסיא, the hidden realm) is on a higher spiritual level than meat (which represent עלמא דאתגליא, the visible world). We thus start with eating fish, thereby giving us the power to afterwards extract the "sparks of holiness" from the meat.
Likely based on "לעולם יקדים אדם דבר הקל ומאחר הכבד" (in my own loose translation, "one should always have the lighter food first and the heavier afterward", from רמב״ם הלכות דעות פרק ד, q.v.).
Harav Akiva Eisenberg (formerly a lecturer at Aish and Ohr, now retired,) told me something excellent. Our preparation and the order of the meal at the Shabbos table is a re-enactment of Ma'aseh Bereishis.
The order of our preparation and of our meals seems to be inviolate, as if it were set in stone. Who would have a fleishige first course and a main course of fish? Yes, I'm sure it is sometimes done, but it's rare. And as you all know, we put the challah on the table before the candles, ostensibly to prevent a muktzeh problem of Basis L'Davar Ha'Asur, although considering the relative value of the silver candlesticks and the Challah, it's not clear why that would work. But here's what Harav AE told me.
Every step of the process represents the order of the creation of the world.
First Day: Tohu VaVohu, inchoate matter was created to later be properly formed- Preparation for Shabbos. Second Day: Spreading out the Heavens- Spreading the tablecloth. Third Day: Desheh Eisev- Placing the Challah on the table. Fourth Day: The two Me'oros- Putting two candles on the table and later lighting them. Fifth Day: Fish- the first course. Sixth Day: Animals- the main course. Shabbos.
Like many of our symbolic minhagim (such as the Kittel at the Seder, please see my post at Havolin Blogspot. com regarding the Teshuva in the Igros Moshe in which he says that the meaning of the kittel at the Seder changes depending on the generation and the locale,) the doer's understanding informs the effect of the minhag. Setting the table while saying "In honor of the holy Shabbos" is an entirely different experience than doing it as a tedious obligation. Here, too, while I won't insist that this is the reason for the order of the meal, I do believe that it was a factor in its ubiquity. In any case, it is worth contemplating.
The sefer אוצר יד חיים, סימן ע writes that the Shabbos song reflects the order of eating meat and fish in earlier times - first meat then fish. And this is why the Shulchan Aruch, Orach Chaim 273,2 says "Between meat and fish there is an obligation to wash (the hands)", again the language reflects the earlier custom. He adds that this same order is mentioned in other halachic seforim.
I heard a while back from Rabbi Levi Garelik that a certain Sefer (I don't remember which) writes that Morranos would eat fish, soup and then meat in that order on Friday night as a secret sign to each other that they were Jewish, and the custom was an adaptation of that practice.
It's not obvious that the order in the song is intended to be a description of the recommended chronology of implementation of a minhag. Maybe it's in order of value per pound, for example. If the order of items in the song is chronological and significant, then the first words of the verse, "Echol mashmanim; shetei mamtakim" ("Eat rich foods; drink sweet drinks"), would seem to conflict with the fact that we have Kiddush before even an appetizer!
Fish were created first, then animals (for meat.)
Historically, meat wasn't always available and could be expensive, fish was not that expensive (comparatively), so fish was a constant and meat was a luxury. Tadir V'Sheino Tadir; Tadir Kodem.
It's brought down that Le'Atid Lavo, we will partake of the meal of Leviathan which is a large aquatic species. Since Shabbos is Me'ein HaOlam HaBa we partake of fish symbolically to represent Leviathan.
Al pi Kabbala, nitzozot of Neshamot are present in fish more readily than meat (since Shechita could be invalidated, etc...) and we want to Metaken the Nitzozot on Shabbat immediately after Kiddush, etc...
To my understanding, it's really just based off of traditional European festive course order (soup > fish > salad > meat > dessert). I know a lot of families who skip out on the fish entirely. Other families skip out on the meat, and then you've got vegetarians and vegans.
Me? I personally go for "everything on the table at the same time" approach, while respecting the minhag of those who avoid putting meat and fish on the same table simultaneously.
The song's order is just so it rhymes!