Because of the Vulcans
In Enterprise, they use a different name: Minshara-class. 1
I would assume that over time, this was shortened to just M.
So that would explain why it's an M, which is smack-dab in the middle of the alphabet, and not at the beginning or end.
Continuing to assume, we might assume that the other letters were decided after Minshara was shortened to M, seeing as they appear to lead up to M being inhabitable.2
The Vulcan term "Minshara-class" (first used in ENT: "Strange New World") was used in Enterprise to denote planets that in other series would have been called class M by the writers, the implied consequence being that the two terms meant the same -Memory Alpha
the implied consequence being that the two terms meant the same, and possibly even that M stood for Minshara. This assumption has been contested by some fans, but is at least supported by the reference book Star Trek: Star Charts. From an in-universe standpoint, the term M-class was first seen chronologically in a text within the Handbook of Exobiology in "Strange New World", the same episode that introduced Minshara-class. However, this mention was barely legible on-screen and may have been included by an art department not yet aware of the intention to use "Minshara class". The first spoken use of the word was in ENT: "Home", in which Archer used it to describe Archer IV, a planet implied (but not confirmed) to be Minshara class in ENT: "Strange New World". The term also appeared on Enterprise's computer displays, indicating that Starfleet adapted it eventually. -Same article as above