Your best bets are probably either the Apple iPod or the Creative Labs Jukebox Zen. Both are nice, with members of each camp strongly supporting their choice (just like the car world). I'd check both out and try to use both before you decide.
If you do buy one I'd suggest buying it somewhere like Best Buy and getting a replacement plan that will cover the battery, the lcd, and whatever else might go wrong as they are very expensive to fix as noted above (though they have been improved, battery technology isn't where we'd like it to be and the battery will die). Good luck, they're both nice players and I'm sure you'd enjoy either one.
-Jade