Coming into Shabbos Chanukah, one must first light the menorah, and then Shabbos candles. The logic is straightforward – once you have accepted Shabbos you can no longer light the Chanukah candles. It would seem sensible that on Motzai Shabbos the order would be reversed. First make Havdalah and close out Shabbos and then light the menorah. This is however not so simple, as we shall see.
Counter intuitively; the Shulchan Aruch (OC 681:2) simply states that in shul the menorah should be lit before Havdalah is made. The Rema adds that at home one should definitely do so because he has already made Havdalah, and thus ended Shabbos, in Shul. Concurring with the Rema is the Elyah Rabbah, Magen Avrohom, Vilna Gaon, Chemed Moshe, Beis Meir (who brings a proof from the Yerushalmi), and the Yaavetz. In fact the Yaavetz quotes his father, the Chacham Tzvi, as having laughed at those who lit Chanukah candles before Havdalah. He writes that his personal conclusion was that one should indeed light the Menorah first, and in his responsa he refutes the opposing proofs.
The Mishna Berura explains: Although there is a general principle that when presented with two mitzvos one should do the more frequent one first, when it comes to leaving Shabbos we want to delay it as much as possible. The Beis Shearim (OC 396) contrasts this with the idea of ‘zrizim makdimim l’mitzvos’ that one should rush to do a mitzvah to show how beloved it is, so too one should be hesitant to end Shabbos thus showing how precious it is.
The Maharal writes that one should make Havdalah first, out of concern that he may forget to say Havdalah earlier (in the Amidah, or by saying Baruch Hamavdil Bein Kodesh Lchol). He will then wind up lighting the Menorah before he has personally ended Shabbos. Thus, to be safe, one should make Havdalah first. This is also the opinion of the Taz, Malbushei Yom Tov, Pri Chadash and Derech Chaim. Although the Maharal extends his line of reasoning to the Shul lighting as well, the others who concur with him limit it to lighting at home (thereby only arguing with the Rema and not with the Shulchan Aruch).
In response to the Mishna Berura’s explanation that we want to delay leaving the Shabbos the Pri Chadash writes: As soon as one does Melocha such as lighting candles he has de facto ushered out Shabbos and therefore may as well have made Havdalah. The Elyah Rabba responds, that until one makes Havdalah over wine, even if they have recited ‘Boruch Hamavdil’ and done Melocha, there are still remnants of the holiness of Shabbos.
There is an additional rationale to lighting the Menorah first. In theory one can make Havdalah all night, but the Menorah ideally must be lit right when it gets dark. Once the hour is such that people are no longer found in the street, one may very possibly have forfeited the mitzvah to light the Menorah. Therefore, say the Avnei Nezer and the Yaavetz, one should immediately light the menorah before Havdalah.
The Mishna Berura concludes that in Shul one should follow the Shulchon Aruch and light the Menorah first, at home there is Halachic legitimacy to both sides of the argument and either way is alright.