ffmpegx
If you are encoding DVDs, use Handbrake- it is easily one of the best and easiest free applications for this.
For transcoding divX/xvid files, I use fmpegX with pretty good results. It isn't as user-friendly as it could be, since it is very possible to use settings that will not work on the iPhone, but once you find what works, it's very easy.
http://www.ffmpegx.com/
ffmpegX has an "ipod" preset for H.264 encoding, of which I just modify the bitrate, resolution, and audio encoding parameters. I always cut the resolution down so that either the height or width is one of the iphone's default resolutions. There is no point in carrying extra resolution, right?
I choose 600-800kbps video for TV shows and movies, 400kbps for cartoons, and transcode the audio down to 96-128kbps aac (especially if someone has it in 256kbps mp3 or something silly like that).
What comes out is a pretty small file that still looks really good. You can get a 20 minute TV program in at 100mb that looks the same as something twice as big, since you are taking advantage of encoding specifically for the iphone screen.
On a slightly related question, what do people use for transcoding audio to aac? I have a bunch of albums in vorbis format that I need to switch over, and every program I find wants to charge me $20 for this incredibly simple task. I want it to keep tag information and be able to batch process several gigs of music without me putting in much input.