(a) That is an excellent point. The order the Gemara gives is that the three Se'udos saves from Chevlei Mashi'ach, Gehinom, and the war of Gog and Magog - which would seem to be in no particular order. This is also the order of the Pesukim that are brought for proof, and the way our Gemara is quoted in Yalkut Shimoni 1:258, 2:377.

Some early works do cite the Gemara slightly differently; they switch the order and put Gog u'Magog before Gehinom (Seder Hayom, Toras Haminchah of Rav Yakov Sakili). But they probably just switched the order in their quote.

In Yalkut Shimoni a different statement is made about how observing Shabbos (1:261) and the Mitzvos (2:932) saves one from "the day of Gog u'Magog, Chevlei Mashi'ach, and the Great Day of Judgment. This would seem to be a more intuitive sequence, as Gog u'Magog (the war preceding Mashi'ach ben David's arrival) is followed by Chevlei Mashi'ach (the dreaded difficulties that ensue during the process of Mashi'ach ben David's arrival and conquest).

(b) Regarding the order of our Gemara, I found that Rav Tzadok Kohen writes that Chevlei Mashi'ach applies to each and every generation. Every generation has a Tzadik who contains a spark of Mashi'ach within him (and apparently either he or those who live in his generation bear with him some level of Chevlei Mashi'ach).

If so, we may suggest that Chevlei Mashi'ach is first, then Gehinom (after death), and Gog u'Magog is saved for last, since it only applies to those who are around to see it when Mashi'ach actually arrives.

(c) But I would like to suggest another reason for the strange order.

The Shem Mishmuel (Beha'aloscha 5673) points out that the three meals of Shabbos correspond to the three Patriarchs. Just as each forefather instituted a Tefilah for a different part of the day, each has a Shabbos meal during that same time of the day which corresponds to him (and his Tefilah). Thus, Yakov's is the evening meal, Avraham's the day meal, and Yitzchak's the afternoon meal.

With this in mind, it is easy to see that although the evening meal is the first, chronologically, it is really the last in the logical order, just as Yakov is the last of the Avos. This is not by chance; although our day begins at night, in areas dealing with the Word To Come the day comes before the night (as we find with regard to Korbanos and Torah, Yomam v'Laylah - I discussed this in my Chanukah talk for 5772, and elsewhere). And Shabbos is me'Ein Olam Haba, so we can appreciate why the night meal is in a certain sense the "last" of the three. One might even say that Shabbos starts from the morning - and continues to the evening meal of the following Shabbos!

If so, the order in the Gemara corresponds to the order of the meals that save from each of the three Pur'anos: the evening meal from Chevlei Mashi'ach, the morning from Gehinom, and the afternoon from Gog u'Magog. But they are out of order - since the first meal (the evening) is actually the one that saves from Chevlei Mashi'ach (the last salvation, after Gog u'Magog) - because that meal has an aspect of being the last of the three, as we explained.

Best regards, Mordecai Kornfeld