What, no ogg?
MP3 should be playable on just about everything.
The MP3 format has a lot of options for compression. The HD thing is just MP3 with all compression turned off. The files you'll get will be large. (I'd guess 30-40MB per song)
The other MP3 format is the same but with whatever compression options they think are appropriate turned on. (Smaller, but not pure)