Smaller Replacement for my Zen Xtra

I loved the functionality of my Zen Xtra (if not the size), but the USB port died over the weekend, and even if I send it to Creative to fix (which I hear will take forever and may not even work, anyway) they will erase my hard drive. If I'm going to start from scratch, I might as well do it with something newer and smaller, but I'm having problems finding anything that compares. I like being able to search for a song by artist, title, etc. And I like being able to play an album in the order designated by the artist without having to rename the tracks alphabetically or with numbers. I have over 4000 songs in my library - luckily the vast majority are backed up on my external hard drive, so it will only be a small pain to get them onto a new player. Who has a non-iPod suggestion?