The Zune HD has alphabet search. Apparently the OP never noticed. Music>Songs> Tap an icon to bring up the alphabet, then tap U (or Z) to jump to all the songs beginning with U (or Z), or if none exist then the next closest letter among your songs.
The Touch does a fine job too. Either device is great.
The Zune HD does indeed have a search function (letter search) which is really handy. If the OP returned the Zune HD because of this, it's kind of ironic.