Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Quicktime Pro lets you optimise files for broadband/dialup etc and also lets you compress or change the audio properties. It's cheap enough too. Also, I think DIVX lets you do this, but they might charge for the privilege.
http://www.3ivx.com/
 
I haven't done much myself with mp4 but Im guessing ffmpeg and ffmpegx handle it, and they're free.

QuickTime Pro is like $29 and does have a few nifty features including the completely one-click encoding for video iPod and other common video standards.

iMovie (part of the $79 iLife 05 suite which has a bundle of really good apps) also does mp4 just fine. And with Quicktime 7.0.3 (non-Pro even) it directly supports the export to video iPod option, so you don't have to pay $29 + $79 if that is your goal.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.