I am pretty sure that Constellation was the first M class ship Solsticized in April of 2011. However, at that time they had not figured on adding the new cabins on deck 12 back then. I think they will be added on the next dry dock.
I understand what you're saying regarding the balconies on Galaxy & Mercury, but they could have added many balconies like they did on Century, which is probably why she is still in the fleet, & not them, but for how long, who can say. In fact it would have been better to keep them rather than Century because they have 2 pools to Century's 1.
Anyway, it's nice to have our choice of so many different types of ships. I think there are still many out there who prefer what is now considered ships, even though when they were built in the late 90s & early 2000s, they were considered the largest ships afloat! How times change!