I prefer entire albums for the most part too, but I have jumped into the digital music world also. It's just too darn handy! I just use WMP (not Wily Mo Pena) to organize things on the PC and it works fine for me.
My player (Mobiblu cube 2GB) is definitely not for everyone however, but I love it and have had 100% positive experience with it. Plus I am kinda "gadgety".
http://www.mobibluamerica.com/dah1500_20060208.htm
The cube doesn't display pictures or anything like that, but it works well for what I wanted it for. As others have said, you just gotta choose what you think works for you. I knew I wouldn't want pictures/video (out of my 1st player anyway) so I narrowed my search quite a bit up front.
My wife has a San Disk Sansa 4GBwhich is really sweet and she loves it. I'd get that one again in a second also. Plus the battery is user replaceable and has great life.
My next step is linking up home stereo in some manner to take advantage of digital music storage on our PC.