Enter Videora Converter, which can transcode just about any video format (including AVI, FLV, and VOB) to iPod/iPhone-friendly H.264 or MPEG-4. A new 4.04 version was just released, and it's better than ever.
It's not, however, the most user-friendly program in the world, so here's a quick walk-through:
-- Download and install the proper version for your device (there are six versions of Videora, one each for the iPod Video, iPod nano, iPhone 3G, etc.).
-- Run the program, then click the Convert button.
-- Click the Video File tab, and then choose Normal Mode (unless you're an advanced user, in which case you may want Power Mode).