teddy, there are many flavors of MPEG-4 video, which one are you using? Changing to a different format is not going to save you a lot of space. MPEG-4 video is state of the art and even competing codecs do not give better compression rates.
Some compression schemes can use advanced features to save space, but these features put an extra burden on the decompression hardware. For example, with MPEG-4 AVC you can use CABAC, but some decoders can't handle this. As far as I know, the iPod can't playback this kind of file.
Here's another idea. If you are using a constant bitrate (CBR), changing to a variable bitrate (VBR) should save space on most videos without a loss of quality. The trade-off here is again increased requirements on the decoding hardware, but decoders that can handle VBR are quite common.
Finally, if you have a target size that you need, e.g. 700 MB for a CD-ROM, then set your encoder to that size and let it choose the best quality it can.