I've had a long history of mp3 players staring off with a 32Meg yeah you heard right RCA Lyra. It was crap it was replaced by an iRiver which I got from Best Buy with a replacement plan. I've milked that replacement plan for a 128M to a 512M to a 1Gig, 8G Sansa and now a 30G Zen. All at the cost of renewing my replacement plan and paying any price difference.
Here is what I can share.
iRiver players amazingly great feature loaded units my 1G iRiver used a single AA bat that lasted 20-30 hours, it had voice recording, line in recording, FM recording, Custom EQ and a few other cool features. The units are all very solid have lots of great features the firmware is very stable. Right now the hot players to own by them are the new Clix2 there is an 8G unit which has a great user interface. The whole faceplate of the mp3 player sits on a micro switches so you just press the top of the screen to navagate the unit. The software that comes with it is simple but works.
Sansa by Sandisc this unit was a nice unit it had a small screen but it worked pretty good after a while it just started to flake out. The unit used to lock up quite a bit the firmware for the player was crap. If you get the player from Best Buy it comes with Rhapsody (not the band) loaded on the player and it will always remain on your menu system. If you try to setup the service on your PC its a huge pain to remove it from your player. It uses Windows Media Player to sync your songs to the unit or you can use its own songs.
Creative Labs, my current player is the Zen Vision M, a 30G HD based unit which I dont think Creative Labs is making the HD units anymore more on that later. This player is thicker than an iPod but its a great unit the screen on it is fantastic, it has voice recording, custom EQ, FM tuner, it supports video play back, and the usual set of features. The battery life is nothing great, compared to the flash memory based players. The thing that is awesome for the Zen VM is you can hook it up to a TV and watch videos / movies saved on it. At the hotel room at PP I had my player loaded with all these metal videos we just hung out drank and watched all these videos on the TV in my room, its also cool to take to a party too. I have a few killer shows loaded up on it that we watched at a friends party just bring your charger with. The files on the unit can be saved by drag and drop, which means you can copy mp3 files to your player and load them on another pc if you want no copy protection shit on it these units.
Give the industry another 8 months and I think you wont see any HD based players that are under 60G the reason is that flash memory manufacturing is getting tooled up to the point that we're going to see 32G based flash memory mp3 players really soon. Of course the features of these players is smaller size, longer battery life, no moving parts.
Here is a great site for reviews on mp3 players.
http://www.dapreview.net/news.php