1) Rebbi Akiva Eiger, in his commentary on the Mishnah, gives a reason for why the haircut is stated first. In fact, the haircut is not only stated first, but it is also stated separately and not mixed together with the bathouse, leather tannery, eating, and court case. Rebbi Akiva Eiger writes that this is because, concerning the haircut, there is more of a reason to make a Gezeirah not to do it before one has prayed since, in all the other cases in the Mishnah, if one sees that it is getting late and the time of Tefilah has arrived, it is easier to break off what one is doing and daven, but when one is in the middle of a haircut one would not stop since it is very embarrassing to have to break off when a haircut has only been half done. Due to considerations of Kavod ha'Beri'os, it would be reasonable not to make a Gezeirah.

2) We learn from Rebbi Akiva Eiger that it is logical that the first example mentioned in the Mishnah should be the one for which there is most reason to say that it should not be done before Tefilah. I have not found in the Mefarshim any explanations about the order of the other parts of the Mishnah, but I am going to make my own suggestions based on the hint that we have received from Rebbi Akiva Eiger.

3) The next example mentioned by the Mishnah is the bath-house. This is presumably something similar to a sauna. If so, we can understand that there is a good reason to make a Gezera since it is more probable that one will not stop in the middle in order to pray because, again, there might be inconvenience and also embarrassment involved in getting oneself dressed in a sufficiently dignified way to be able to daven Shemoneh Esreh on time.

4) The next example is the leather tannery. In this case, there is no embarrassment involved in breaking off one's activities, so there is not quite as much reason to forbid as there was with the haircut and the bath-house, but since this is an activity that people do in order to earn their livelihood, there might still be a significant temptation not to break off, so there is a good reason to make the Gezeirah not to start once the time of Minchah has arrived.

5) The next example is starting a meal. Here, the necessity to make a Gezeirah is even less because it is not difficult to break off for Minchah in the middle of the meal and pray in the same room as one is eating.

6) The last example is the court case. In this case, there is the least necessity to prohibit starting before Minchah because distinguished Dayanim are present in the Beis Din room and it would be most unlikely that a person would forget to pray. This is why the Mishnah tells us, at the end, that even so we are afraid of the person forgetting to say Minchah and therefore we prohibit him from commencing the court case near the time of Minchah.

7) According to the above explanation, the Mishnah follows the style of "Lo Zu Af Zu" -- "Not only is this forbiden but even this is forbidden," because the Gezeirah in each case is a bigger Chidush than the preceding case.

Kol Tuv,

Dovid Bloom

I saw that the Rambam writes i his commentary on the Mishnah that the reason why this Mishnah appears here -- even though it has no connection with Shabbos -- is that these Gezeiros are part of the 18 Gezeiros mentioned below on 13b in the Mishnah. The Rambam also writes that the reason why the Mishnah on 9b comes before the Mishnah on 11a (that a tailor must not go out with his needle), may be because "Al Zeh ha'Seder Hayu ha'Gezeiros b'Oso ha'Yom." The Rambam is referring specifically to the posssibility that the Gezeiros in our Mishnah were made before the Gezeirah of the tailor and the needle. Howver, it is also possible that within our Mishnah (9b) itself, the order of the Gezeiros follows the order that they were issued on that day.

Kol Tuv,

Dovid Bloom

I posed your question to a Gadol and he replied: "Mah d'Shech'iach Kodem" -- "What is more frequent comes first."

The Mishnah mentions the most common activities first and afterwards the less usual activities.

Kol Tuv,

Dovid Bloom