I can't import a M3u playlist to have it on the Zune. (The following might not be fair, but it still annoys me) Doesn't handle playlists how I would want it to - can't have playlist and drill down to artist, album. Adding Classical music is just a mess of artists, so want it in a separate playlist. The software is as bloaty as itunes.
Having to middle click to select artist, album etc is terrible. I miss it and go sideways often. Getting your passenger to do it who is not familiar with it is next to impossible.
If you gone back one too many times, you then press back again until the track is on now playing. If you press back again now it will go back to the starting menu where you select music etc.
No simple way to get random on and off.
The device has no idea how much battery life you have. Seems to go from 3/4 to empty instantly.
Rubbish lossless support, and it seems to crash if a track size is over a certain size. Not good when a lot of tracks I listen to are over 10 minutes long.
As said, the only redeeming feature is the DAC is very good.
I have .m3u playlists on my zune? They import accross just fine.
Software as bloaty as iTunes? It opens when I plug my zune in, automatically updates the library and transfers it accross. It runs one very small program in the background whereas iTunes iirc runs 2? iPodHelper and iTunesService? It doesn't slow to a crawl with big playlists like old versions of iTunes did and it generally does nothing wrong. Honestly don't get you with that one. It's hardly a foobar2000 but, eh, what can you expect?
Classic music is fine when you have it set to display album artist rather than album and track artist.
Can't say I've ever had the middle click being a problem, that's just because people are used to other players!
The back button behaviour I can understand how it can bug some people but it suits me down to the ground. Plus easy enough to get back to artist/tracklist by going middle click - go to tracklist/artist.
Simple way to get random on or off? You go and change the song

Or you middle click turn shuffle of if that's what you mean.
Battery I also had problems on, lookup how to do a full calibration on the thing and it sorts it right out, am getting a good 15+ hours out of mine now compared to the pathetic times before.
Lostless, fair play, it lacks in that respect, but I can't say I've ever had crashing problems and have a fair lostless collection on the device. iPods don't exactly haev wild lostless support either though? ALAC only is it not?
Just wish we could have the Zune marketplace over here, that's by far the best deal in legal music going.