I am actually glad that not all the music will be orchestral. Not all the games being represented in SSBB need or fit well with orchestral music. This is not to say that I do not like orchestral music, I love it, I just feel that variety is best.
Regarding the new mix on the site, I could tell that it was done by someone who worked on the Wild Arms series, because of the somewhat prominent western (as in cowboy) motif, and I think it would be a crime not to have the Gerudo Valley Theme be part of it, and I do not care if it is not one of the tunes played on the ocarina.
Regarding Sheik's gender, I always figured that after Zelda reveled that she was in fact Sheik that it was pretty solid that Sheik was actually a Female. I did not think there was anything like a Ranma or Berg Katse thing going on. At most one could say that Sheik is supposed to be heavily androgynous, like the Statue of Liberty (everyone assumes it is a she but it is not), so that when playing OOT one would not be sure who was behind the mask. As for the use of "He" in the game script, it is convention in common english to use masculine pronouns in the case of an androgynous or genderless entity (person or animal). It is also part of human nature to usually assume that an entity that appears androgynous or genderless is in fact a member of one's own gender.
The more I think about it though the more I would like to see Human Midna take Sheik's place as Zelda's transformation, keeping all the same moves of course. I think that SSB is ready for a hot redhead.