Just music/audio, none of the flashy stuff like video etc?
I've said this so many times now I may be accused of working for them, but honestly no connection. For basic, good, easy to use and lighter on the wallet you won't go wrong with the SANSA range. In fact I'd even say the SANSA Clip (think it's Clip plus now) will be perfect.
You'll need some form of library to store the music you upload from cd as you'll have to take the songs and convert them MP3 or whatever format. It's a doddle so don't worry.
With WINAMP (if you're a Windows user) you can do this and organise playlists (just collections of songs you like or along a theme if you end up getting really geeky about it).
Look for an MP3 player that is drag and drop, i.e. you just open the folder "My Music" select the songs you want and drag them over the the MP3 player (once connected) as if you were putting files onto a USB stick.
I'm an iPod guy myself, but have a SANSA Clip for the running and cycling. It is way better than the iPod shuffle and other smaller devices. It's simple and easy, has a radio too, has a specific option for audiobooks (it automatically "bookmarks" them so you don't lose your place if you listen to something else) and erm...it clips to your belt?