The Tears of Eridanus
This one was really fascinating in that we got to see an alternate version of the Federation that was not dominated by human ideals, but by Andorian ones, and for humanity to finally become the minority.
I agree; it was rather refreshing, and I think the writing successfully demonstrated how this version of the Federation was both familiar and distinct. To tie in somewhat with your points about a more straightforwardly military fleet, I really liked the ceremony with the flabjellah; seeing the familiar Federation ideals filtered through a warrior culture's perspective was most enlightening. I also liked how this union wasn't presented as being inferior or superior to the more familiar Federation, but simply different. Functional in different ways; less than perfect in different ways (the decimation of the Xindi was indeed disturbing, but the implied clash of perspectives in the modern fleet looking back on that part of its history was very interesting). I suppose overall the story's strength is that it presents "the Federation" struggling with itself and the nature of its core values and history in ways that differ from what's possible in the mainstream 'verse, and therefore it justifies itself as a "Myriad Universes" story. Human protagonists who are filtering their perceptions through an Andorian-coloured prism; very intriguing.