Strictly speaking of music, mp4 sounds better than mp3 at the same bit rate (commonly 256 Kbps). Why? because the slices of the mp4 file are spaced more closely together. This results in more slices over the length of the audio file. The result is cleaner high frequencies, cleaner mid frequencies, and cleaner low frequencies.
An mp4 file is larger in size for a 3 minute recording than an mp3 for the same recording. The result is higher fidelity.
Consider this: More sampling per second gets you better fidelity. Because the sampling occurs more frequently, more bits for any one second results in cleaner sound. For a 3 minute song, the file size will grown about 10-15%. That difference makes for smoother transistions and less loss. THerefore, the sound quality improves.
However, built in to mp4 is the ability to sample both audio and video. A video in mp4 vs the same video with AAC video and mp3 sound, is somewhat smaller (not much), but the mp4 video contains both the video and the audio and you still get noticibly better sound (but not as much for an audio only file). Stil, the quality fo the audio can be heard, but not as much as you'd get for an audio only file.
So, the bottom line: For the best audio only sound, use mp4. For a little bit better audio in a video, use mp4 again. The trade off is the file size, but with today's Terrabyte sized solid state drives, there is more than enough room for the extra size in the mp4 file. WHAT REALLY MATTERS is the sound that reaches your ear. File size means nothing. Sound quality is everything.
If you compare the same Mp4 file against a recompile at mp3 at the same bit rate, you WILL hear a difference. Though it is barely noticable, it is noticable.
To get the best, get mp4 files. To get the very best, get AAC files (uncompressed) or Wav files (uncompressed). But you'll find that there is barely noticable difference between the uncompressed and the mp4 compression. But if you compare the uncompressed to and MP3 (highest bit rate possible is 256 KBps), you will hear a noticable difference.
Bottom line: MP4, because it takes more samples than an mp3 in any given time period, produces the better audio. The other choices that are uncompresssed result in the best sound quality (depending on type of sampling [SAAC is preffered]), you'll have file sizes that are considerably larger with no hardly any discernable difference in sound quality over the 256 kbps mp4, but a huge difference compared to a 256 kbps mp3 file.
So, when in doubt, always choose the mp4 file. You can save extra space by converting to mp3, but if you start with the mp3 and convert it to mp4, you'll gain nothing because the mp3 is already degraded.
Your best source for mp4 is iTunes. Amazon sells variable bit rate (ugh) mp3 files in their digital downloads, and these sound terrible! I know. I've been there, done that.
Re: Older songs and albums at iTunes. Don't. Just plain don't. It is my experience that these files are mp3s that have been converted to mp4. If you can find a remaster, then the tapes used to make the album have been cleaned, and the new file starts with mp4 format. Get these. Avoild older music that does not say 'remastered', or your audio will suffer and you'll soon be watching for the remaster.
A personal experience: I was strapped for money, but wanted to replace my 128kBps Sgt Peppers album, so I bought the album from Amazon which uses variable bit rate. Two songs had the vocal buried. These were "I Get By With a Little Help From My Friends" and "When I'm sixty four". So I fired up my audio converting software and it told me that both of these tracks downgraded the sampling to 64 kbps! That is unacceptable. Would amazon replace thes tracks? No. They could not. So I hopped over to iTunes and got these two at fixed bit rate 256 kbps mp4. This solved the problem. Still, the rest of the album suffered because variable bit rate mp3 was used. I eventually replaced the whole album (spending nearly twice as much) by buying it from iTunes which always uses mp4. The result, in comparison by track to track, was incredibly superior.
So always look for fixed bit rate mp4 files. This is itunes' standard, albeit some of the older music has not been cleaned on the tape, and these suffer because that tape has not been cleaned (of noise and hiss and pops). But if this is your only option, get the album, then wait for a remaster from tape. You'll have the album and can upgrade it soon enough.
Mp4 wrocks over mp3. There is no question about it. Why? More samples per second (video sampling slices are used along with the audio sampling), and the audio improves considerably.