The proper order of these blessings is a machloket between Rav and Rabba bar bar Chana on Sukkah 56a. Rav held the blessing on the Sukkah comes first because it's the obligation of the day and Rabba bar bar Chana held that Shehechiyanu comes first because it is Tadir = said more often. The Rambam (Sukkah 6:2) rules like Rav and Shulchan Aruch does likewise in OC 643:1.
The Tur (OC 661) quotes two opinions regarding the second day. The Rosh holds that the order should be flipped and the Avi Ezri holds that the order should remain the same. At first glance the Avi Ezri makes the most sense: when else do we distinguish between the different days of Yom Tov? We say a Shehechiyanu on the day in case it is really the first day, shouldn't we say a Shehechiyanu on the Sukkah in case it is really our first time performing the mitzva?
The answer lies in the nature of the Shehechiyanu on the Sukkah. It is not being said on the new mitzva performance, but rather is said upon building the sukkah and can even be said many days before the holiday starts (OC 641, note also our custom to use the Shehechiyanu on the holiday to fulfill this obligation). Thus even if the second day really is the right day, we have already fulfilled the obligation of Shehechiyanu on the Sukkah the previous night. (This is also why we don't say a Shehechiyanu on the Lulav on the second day of Sukkot, but we do on the Shofar on the second day of Rosh HaShana.)
(I'll note that neither Rav nor Rabba bar bar Chana seemed to care that the Shehechiyanu be after the Sukkah in order to have the Shehechiyanu apply to the Sukkah as well, ie Shehechiyanu should apply to everything by default anyway. Tzarich iyun on the Rosh IMO.)
The Shulchan Aruch and Rama rule like the Rosh, while Bach, Maharshal and Gra rule like the Avi Ezri (see more names on both sides in Shaar HaTziyun OC 661 sk 3) and hence the differences in custom.