If you're using lossy compression like WMA or MP3, there will always be people who think that it will never be good enough. Finicky golden-eared audiophiles shouldn't be complaining anyway. After all, you're using a portable player. There have been studies on whether normal people can hear any differences between an MP3 and its original CD track. Here's one of them, from the German magazine C't:
http://www.geocities.com/altbinariessoundsmusicclassical/mp3test.html
You may or may not agree with their methods or their findings, so this study won't settle anything. For one, the article doesn't mention which encoder or encoder settings were used to prepare the MP3s.
Here's the short version: most people can tell the difference between the original CD and a 128K MP3, but when they weren't told which one was which, they sometimes judged the 128K MP3 as better-sounding. They also found that most people cannot tell the difference between a 256K MP3 and the original CD.
So just experiment a little and trust your own ears to find the right balance between quality and size. This is probably the most practical solution for you.
Another approach would be to disregard file size and encode using the highest-quality settings available (maybe even lossless if you distrust the C't study and you have a large, hard-disk player that will play those big files).
This is impractical for many people, but it might be the more future-proof solution because flash memory and hard drives are almost always getting bigger and cheaper. Some time in the future, maybe 10 years from now, the average person will be able to hold his or her entire music collection on a portable player, even with lossless formats. If you RIP using the highest-quality settings now, you won't need to do it again should you want better audio quality later (assuming of course that the dominant media formats would still be the same when that day comes--this is a big if).