Baruch she'Kivanta! This is an excellent question and is asked by the Mefarshim. No, one does not have to say that there is a Machlokes between the two Gemaras, as will be explained b'Ezer Hash-m.

1.

(a) The Sha'agas Aryeh (#50) cites the Gemara in Menachos (64a), which you mentioned, in which Rabah says that even if a person has already slaughtered the thinner animal as a Korban but has a nicer, fatter one available, we tell him l'Chatchilah to bring the fat one and slaughter it on Shabbos. The Sha'agas Aryeh proves from this Gemara that even for "Hidur Mitzvah," a Korban offered in a more beautiful way, one may override Shabbos.

(b) The Sha'agas Aryeh asks that according to this, why does the Gemara in Shabbos (133b) state that if the Mohel has already removed ("Piresh") his hands from the act of the Milah, he may not return to the Mitzvah even though, if he were to do so, he would be able to do the Milah in a nicer way? The Sha'agas Aryeh answers that one must say that because the mohel has already been "Piresh," he has completed the Mitvzah of Milah. If he were to return to the Mitzvah, this would be considered a new start. Once one has completed the Mitzvah there is no longer any Inyan of "Zeh Keli" to restart and do the Mitzvah in a more beautiful way. Accordingly, on a weekday, one also would not go back for Tzitzin she'Einam Me'akvin.

In summary, according to the Sha'agas Aryeh, "Zeh Keli" means that if one is in the middle of performing a Mitzvah, he should do it in the nicest way possible, but it does not mean that if one has already completed the Mitzvah that he should go back and start up again and do it in a nicer way.

2.

(a) I found another answer to your question in Teshuvos Ein Yitzchak (Even ha'Ezer, vol. 1, 80:9), by Rav Yitzchak Elchanan Spector zt'l. He answers that offering Korbanos on Shabbos is entirely "Hutrah," it is totally permitted. This can be understood based on the Gemara in Yoma (46b) which says that while "Tum'ah" is merely "Dechuyah" for the public (Rashi explains that even when the majority of Klal Yisrael are Tamei the Korban may be offered, nevertheless this allowance was applied only when there was no way to bring it in a state of Taharah), the Korbanos on Shabbos are "Hutrah"; they are entirely permitted. This is why we tell the person to go and slaughter a fat animal, even though he could offer a valid, thinner one. There is no limit to the permission of the Torah to bring Korbanos on Shabbos.

(b) In contrast, perhaps Milah on Shabbos is only "Dechuyah" (or at least is not totally "Hutrah"). There is a source for this in the Bi'ur ha'Gra (YD 266:25), who writes that Shabbos is certainly only Dechuyah with respect to saving a life, as the Rambam writes (Hilchos Shabbos 2:1). The Vilna Ga'on writes that while Korbanos are definitely "Hutrah" on Shabbos, it is possible that Milah is "Dechuyah" and not "Hutrah." (It is not clear what the conclusion of the Vilna Ga'on is, but one nevertheless sees that Milah is less "Hutrah" than Korbanos.) The reason for this difference between Korbanos and Milah is that the Torah says explicitly to offer Korbanos every Shabbos, which means that the Torah wants this to be done absolutely l'Chatchilah, and thus there are no limitations to how one brings Korbanos on Shabbos. In contrast, not every Milah is on Shabbos; only if the baby was born on the previous Shabbos is his Milah on (the following) Shabbos. Hence, Milah on Shabbos is not absolutely l'Chatchilah. (See Shabbos 156a, where the Gemara says that one who was born on Shabbos will die on Shabbos because his birth involved Chilul Shabbos. It is evident from there that the Torah does not ideally want the birth and Milah to be on Shabbos.) Accordingly, there are limitations with regard to what parts of Milah override Shabbos, and thus one does not go back for the Tzitzin she'Einam Me'akvin. Since there are no limitations on bringing the prescribed Korbanos on Shabbos, one may slaughter the fatter animal even though there is a valid, thinner one easily available.

(I have elaborated on what the Ein Yitzchak writes, but I believe that what I have written is what he intended.)

Kol Tuv,

Dovid Bloom

Aurel - thank you for your very kind comments.

I cannot understand the story about the mohel being told to go back and fix it because the Shulchan Aruch Orach Chaim 331:2 states explicitly that on Shabbos if the Milah was finished one only fixes Tzitzin ha'Me'akvin. (Possibly the Talmid Chacham among the guests held that in that particular case what the Mohel though were Tzitzin she'Einam Me'akvin were in reality Tzitzin ha'Me'akvin.

Yasher Ko'ach

Dovid Bloom