There are essentially two types of music format, the compressed, like MP3 and the uncompressed, like WAV.
In music all compressions (that I can think of, anyway) are lossy. An MP3 file will not sound as good as its source, given ears and equipment which can distinguish, however, for most purposes, MP3 files are adequate. (They actually are better in some circumstances, eg for use in a car, as the compression is not just about file size, but also includes some audio compression - which makes the quiet sounds louder and the loud sounds quieter - ideal in a noisy environment.)
The files you cannot copy to your phone will have digital right management enabled on them, I think all iTunes downloads have DRM, but this isn't the case from other sites or for files you rip yourself.
I'll leave others to recommend software for you, I don't really do much in the way of editing and conversion.