First you need to define a key to 'group' all company elements together that share the same first letter
<xsl:key name="companyLetter" match="company" use="substring(text(), 1, 1)" />
Next, you would iterate over all company elements
<xsl:for-each select="options/companies/company">
However, you only want to process a company element if it is the first occurence of that element for its first letter. You do this by looking up the first element in your key for the first letter, and seeing if it is the same. Element comparison is done using the generate-id() function
<xsl:variable name="firstLetter" select="substring(text(), 1, 1)" />
<xsl:if test="generate-id(.) = generate-id(key('companyLetter', $firstLetter)[1])" >
Putting this altogether gives
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
<xsl:key name="companyLetter" match="company" use="substring(text(), 1, 1)"/>
<xsl:template match="/root">
<select id="colors">
<xsl:for-each select="options/companies/company">
<xsl:sort select="text()"/>
<xsl:variable name="firstLetter" select="substring(text(), 1, 1)"/>
<xsl:if test="generate-id(.) = generate-id(key('companyLetter', $firstLetter)[1])">
<option>
<xsl:attribute name="value">
<xsl:value-of select="$firstLetter"/>
</xsl:attribute>
<xsl:value-of select="$firstLetter"/>
</option>
</xsl:if>
</xsl:for-each>
</select>
</xsl:template>
</xsl:stylesheet>
For the second drop-down, you can use a named template that gets passed a letter as a parameter. You can look up all elements for that letter using the same key as above.
<xsl:template name="Companies">
<xsl:param name="firstLetter"/>
<select>
<xsl:attribute name="id">
<xsl:value-of select="$firstLetter"/>
</xsl:attribute>
<xsl:for-each select="key('companyLetter', $firstLetter)">
<xsl:sort select="text()"/>
<option>
<xsl:attribute name="value">
<xsl:value-of select="@url"/>
</xsl:attribute>
<xsl:value-of select="text()"/>
</option>
</xsl:for-each>
</select>
</xsl:template>
To call the template, it is simply a case of passing the required parameter, for example
<xsl:call-template name="Companies">
<xsl:with-param name="firstLetter">B</xsl:with-param>
</xsl:call-template>
Of course, you could put this is an for-each loop if you wanted to show all drop-downs for all possible first-letters.