I need to sort the children of the root element by _their_ first child.

I suggest you try this for a starters:

<xsl:template match="/*">
	<xsl:copy>
		<xsl:copy-of select="@*"/>
		<xsl:for-each select="*">
			<xsl:sort select="*[1]"/>
			<xsl:copy-of select="."/>
		</xsl:for-each>
	</xsl:copy>
</xsl:template>