I agree with Fr0g, depends on your equipment as to the quality to use, and that includes your ears. Double blind tests are really useful for deciding the format and bitrate to use for different applications. You could have a great set up, but your ears may still not notice a difference, if thats the case, then congratulations, it means you can encode at lower quality, and get more music on your portable.
In most cases, music on a portable is fine in a well encoded lossy format as Fr0g said, and lossless is probably overkill. I usually use a high bit rate ogg file (about q6) on my portable player, 192kbps mp3 for my car stereo (I don't get any benefit of higher bit rates in my car due to engine/road noise and my car stereo doesn't play ogg), very high bitrate ogg (q8 - q10) on my computer (linked to my Hifi by optical s/pdiff), and original CDs in my HiFi. Those are the qualities that I have found to be satisfactory for my ears with each different bit of equipment, the key is just to experiment.
As for where to get the music, I buy it on CD so I can use it in whatever format/quality I want. Allofmp3 is running again as mp3 sparks now, and has a new licencing arangement, and so far, they don't seam to have gotten into too much controvesy so it may be worth trying that. The best thing about allofmp3/mp3sparks was that you could choose the format and quality of the music you downloaded which was very useful, its a shame none of the more mainstream services such as amazon or itunes don't offer the same level of flexibility and quality.