I rather like the MP3 audio file format. It sounds great to me, and it takes up less space than lossless file formats. It's the format that first took hold, and AFAIK, everything supports it. It's what I started with, and to remain consistent, I still use it. One reason you may choose the mp3 file format, is its ubuiquity. Hence born the name "mp3 player". However, if you are just starting your library, you might choose Ogg. Ogg is an open source alternative to mp3. A lossless open source alternative would be FLAC. With any of these formats, you don't have to worry about the headaches of Digital Rights Management. You can learn to use file transfers from a PC, or just direct download to your cellular device, and use an open source app that supports your format.
Here is an option, to have a server, rather than your computer, do the work:
http://www.youtube-mp3.org → this one disappeared, such is the internet
There may be another site that works for Ogg, but I haven't looked.
Edit: Seems that they have blocked that site's use for the United States. No problem! Use a proxy! I use the following extension for Firefox: One Click Proxy. I had to try a couple of times before I got a proxy from another country. Not the best extension for the task, but I already had it and it works.
After you have downloaded a bunch of music, you may find that each one is at a different volume. You can use a volume normalizer called MP3Gain to set all your music at the same volume.