Concerning your third criterion, you can always just edit your own ID3 tags using a number of programs. I use MP3 Tag Tools.

As for your other criteria, they have iPod shuffles. :P
But I really don't know anything about the smaller players, I would never even consider anything that didn't have at least 60GB of disk space.

What's so bad about the iPod UI? I think it's easily the best way to manage music on an MP3 player.