Sony's CD based MP3 players are worth considering. A CD holds the equivalent of 10-12 albums. A few CDs should hold most peoples collections. Play lists can be included on the CD.
One major consideration should be how the player displays information and how easy it is to find the tracks you want to play. If the display can only show a few characters it is difficult to identify tracks.