I personally use my smartphone to listen music, web radio etc. If you get a decent enough of phone, you can have loads of capacity, as they got good memorycard support (my spica has according to specs support up to 32 gigs)

I have a Cowon S9 myself. Bought it after my second iPod bit the dust in under a year (first one died after 11 months, HDD failure. The second, $40 for S&H since it was under a year died after 9 months.... from HDD failure....).
To be honest, it was a pain to find a Cowon anymodel here in Canada but after all the research it sounded like the best one I could buy at the time. And after using it, I can honestly say it was worth it.
Basics of things like the sound quality is so much better. I loaded on the same MP3's and used the same headphones but it was like night and day in sound quality. Also liked I could just drag and drop my music to the Music folder on the S9.
Other great thing about it is the battery life. When I bought it I was getting 60 hours per charge (Ibought it in Oct 2009). I still have it, still works great and still only charge it once every few days and super rare to die (had to be listening to it for 8+ hour days, multiple days in a row.)
It is also a smaller then the iPod and has external buttons so I can feel where the buttons are in my pocket (had a problem finding the iPod wheel from the outside of my jeans and work pants.) The only catch is that it uses its own special usb cable which if I lost the one I got with it, it would be a huge challenge to buy another. When it does break (hopefully not for a long while) I am going to buy another Cowon device after using my S9 and highly recommend them (though don't use/install their 'loader' software, you don't need it and it was bad).

If you don't need to store much music at once, you could get an iPod Shuffle (2nd Gen I think), and use iShuffle in place of iTunes.

It's what I use to fill my Shuffle with mp3s without needing iTunes. Also lets you put the music on other computers via the iPod, which using iTunes wouldn't allow.

Not to defend Apple, since they're already raping the competition every which way... but the ipod sound is fine, its those shitty white bud headphones they flog will all their devices and everyone has to have to show the world they've got an iPod, that suck.

Those are some terrible earphones. Hell, I swapped out my white buds with a pair of Palm branded ear buds from a Palm phone and the sound quality was nearly double.

The sound is improved from the older models but they still use cheap components. The highest quality mainstream devices are the mid-high Sony Walkmans followed closely by the high end Samsungs; Ipods trail around 5th on quality tables usually.

I use my smartphone with Spotify. Costs $9.99 a month, so it's probably not at all what you're looking for, but it's pretty nice; unlimited access to a lot of music (the Spotify catalogue is pretty good these days), both offline and streaming.

Might be worth looking into.

You know, you can synchronize your iShit with Winamp too....

You would be amazed how well those fail to work :P

Thanks for all the other ideas, Looks like I have an awful lot of research to do.

I've had a Cowon S9 since it was released in Dec 2008. Very good sound with up 4 custom equalizer settings, and the available UCIs (User Created Interfaces) have really enhanced it. The newer version is the J3 which comes with an SD slot. There's also the newer Cowon D3 which runs on Android 2.1 compared to a Flash based OS on the S9 and J3.

I haven't used players from other companies yet since I've had no trouble with Cowon so I can't recommend others. A good site to check is http://anythingbutipod.com/ for a wide selection of iPod competitors.

anything that Rockbox supports is a good choice
SanDisk Sansa e200 (v1/v2) is a good player, 2/4/6 GB internal storage depending on the model and you can use MicroSD card to expand it
if you install Rockbox to it you can also use MicroSDHC cards with it
OF (Original Firmware) only supports MP3, WAV and WMA but with Rockbox you get support for more codecs

I have a Cowon iAudio S7 for years now.
The sound quality is great although I did replace the earphones it came with.
What I like about it is the variety of formats it supports, not just WMA, WAV, mp3 and AAC, but for instance also FLAC.
Firmware updates are regularly released and for some Cowon iAudio types, as well as some other brands, there is alternative firmware at rockbox.org

When I got it, I made my choice based upon sound quality first, supported file types second and storage size third. When I noticed they have regular firmware updates it was an extra assurance I made the right choice.
I never regretted it, even while the user interface could be a better.
When the time comes that it needs to be replaced for whatever reason, it will be replaced by another one from the same brand.

Satisfied Sansa Clip+ user here. I recently installed Rockbox (custom firmware) on it, and added a 16GB memory card. I can now carry all my music, in OGG and FLAC format, in a device the size of a lighter, with a highly customizable UI and very good sound quality.

If you have the opportunity to recharge often (you just need a USB port to do so, and with Rockbox you can continue playback while recharging) this is great stuff. Just plan some extra budget for a micro SD card and good earbuds to make the most out of this nice little device.

Only problems are :
- relatively poor battery life (~10h)
- small and monochrome screen, but very readable even outside (OLED technology)
- nothing too fancy : plays the music/audiobooks you put on it, or FM radio, nothing more

I have a Muvo T100. Simple, small, does only what it needs to and doubles up as a normal pen drive, too. No display that can get scratched (I don't treat my things well. They have to be robust :] ).

Perfect, really. 4GB of music is enough for something meant to be used on the go. I use AudioMonkey to randomly replace what's on there, now and then.

[And I use Sennheiser HD 280 pro with them ... a bit of overkill, but, heck, I don't only use them on the Muvo :) ]

Anything iPod.com

Also, the Sansa Clips and Fuze's have ben proven to objectively provide the best sound quality for the money. Aples sound chips are wretched. Apple needs to introduce a web-based itunes, instead of forcing their consumers to be tethered to a computer for updates to your library/syncing. I have a nano, only because my car has great connectivity with iPod. Sandisks players are infinitely superior, unless your iPod was a fashion piece, and not something you use in any meaningful way,.