This order follows from a straight- forward application of two principles: We always strive to light the Chanuka candles as early as possible (SA OC 672); conversely, we always strive to delay havdala in order to extend the Shabbat and show that it is not a burden on us (see SA OC 293).
Other authorities dispute the Rema. For example, Arukh HaShulchan points out that there is another principle: that the more frequent mitzva (havdala) should have precedence. Furthermore, he states that lighting Chanuka lights is hardly an effective way of extending the Shabbat. First of all, it involves a melakha which is forbidden on Shabbat; furthermore, the mitzva itself belongs specifically to the following day! He concludes that at home it is preferable to make havdala first.
Alongside the ramified halakhic discussion of the ideal relationship between the Chanuka lights and havdala, we find in the aggadah a profound connection between these two commandments.
The Yerushalmi explains the origin of the custom to bless on the fire during havdala. During the first Shabbat, complete darkness never fell. Although the sun set on Friday night, the unique holy light of the "seven days of creation", which enabled Adam to see the entire world, continued to glow.
Only as Shabbat departed did Adam experience total darkness. He was terrified, fearing that the serpent was about to engulf him. HaShem provided him with two rocks, enabling him to create a spark and ignite a fire; then his fear abated (Yerushalmi Berakhot end of 8:5).
Elsewhere, the Yerushalmi describes in almost identical language a holiday that Adam instituted around the time of the winter solstice. As the days became shorter and shorter from man's creation in Tishrei, he became terrified, again fearing that the serpent was engulfing him. When the days lengthened, he was relieved and proclaimed a holiday (Yerushalmi Avoda Zara 1:2).
Extending this idea a bit, we may suggest that the character of Chanuka is parallel to that of motza'ei Shabbat. Until the first motza'ei Shabbat, HaShem provided light for us; after- wards, it became our responsibility to provide ourselves with material illumination. Indeed, part of the purpose of creation was for mankind to take an active part in the world's perfection. (As the Torah states in Bereshit 2:3, the creation "which G-d created to do", and the Midrash explains that He made it so that we would then "do", that is, complete the task.)
The Chanuka miracle has a similar character. Until this time, the Divine providence guiding the Jewish people had a prominent miraculous character. During the Exodus and our sojourn in the Midbar, we experienced miracles every day; once we arrived in the Land of Israel our sustenance was natural but public miracles continued to be a frequent aspect of G-d's help. Over the generations, these revealed and public miracles became less frequent, like the shortening days of the fall season. The miracle of the oil at Chanuka was the last such miracle the Jewish people experienced. Even the military victory at Chanuka itself was a natural miracle, not a supernatural one. Indeed, the gemara tells us that Chanuka was "the end of all miracles" (Yoma 29a).
Yet the "serpent" did not engulf us after Chanuka. After HaShem withdrew the supernatural light of the seven days of creation, He didn't forsake us; He provided us with the means to create our own light. Likewise, after He withdrew the supernatural supervision that guided us until the time of Chanuka, He provided the means for us to guide ourselves according to His will even without revealed miracles. This means is the light of Torah, specifically the light of the Torah shebe'al peh (Oral Torah) whose development began to accelerate around the time of Chanuka.
Not only the light of providence, but also the original supernatural light of the seven days inheres in the Torah of the Sages. This is hinted at in the first passage we cited. The Yerushalmi Berakhot mentions that this supernal light illuminated the world for mankind for thirty-six hours - from Friday morning until Saturday night. The Rokeach (Laws of Chanuka 225, cited in Benei Yissachar) writes that this is the basis for the 36 Chanuka lights instituted by Chazal.
Rabbi Meir's book Meaning in Mitzvot is now available as an e-book through Amazon, ibooks, Google Play and B&N.