Imtoo mpeg encoder does a good job but it costs about £20.00.
I'm sure there's a free m4a to mp3 converter out there somewhere as well, try Cnet.
I've recently swapped management of my I-Pod over to Wimamp, so much better than I-Tunes.
If you're changing players, check out the Creative Zen series, they're good, and avoid the Sony players, their software is a bit rubbish.