I can't recommend any good free programs myself to batch convert...I'd search download.com
Are you using iTunes? I recently had to reorganize my 36GB of songs..that's 7,000 songs xD. Wasn't fun. Now they all have album art and correct names
Also, M4A is far superior to MP3. A 128kbps M4A song = a 320kbps MP3 (or so I'm told, it may not be this extreme). I wouldn't change the M4As into MP3s.