If you encode your own video for watching on various devices and you're looking to save every last MB on your iPhone, it could be worth your time to re-encode at least some of your larger files with more conservative settings. While I, for example, have been copying the iTunes Store's settings and encoding my DVD movies at full dimensions and about 1500 Kbps to really let H.264 shine, the truth is you don't need anywhere near that much data to watch quality video on an iPhone's display. By re-encoding your videos and perhaps keeping them in a special iPhone playlist for synching, you can bring even more of your favorite videos with you in a fraction of the space. Unfortunately, you can't re-encode videos you've purchased from the iTunes Store because of the DRM. This how-to primarily applies to video you download from the web or encode yourself from DVD movies and other sources.
To keep things simple, I'll use Blade Runner as our encoding guinea pig (which runs a length of 1:56) and Handbrake for all the encoding. Following are a few sample screenshots of how far you can compress a movie, along with the settings you can use in apps like Handbrake and TUAW favorite VisualHub to try this out for yourself.