I make alot of movies at work with Premiere, and I have to say that it's hard to get a better codec than the standard mpeg-2 or mpeg-4.
From Premiere, I always export the movie as an MOV (using Animation compression). Then I open that in QuickTime Pro 6.5 ($30) and export the MOV to an Mpeg-4 file. Beautiful quality.
Mpeg-2's are similar, but the compressors are expensive, and adding sound is a bit more tricky.
I also have a free DivX AVI plug-in for QTPro that I have never tried (I don't bother because it's not as well supported) but I bet that may work well. I'll test it when I have a minute.
[edit: Okay, I just tested the DivX AVI export from QuickTime Pro... not bad. It took a 70-second 902-mB MOV file (in NTSC format, 720x480 @ 29.97 fps) and spat out a pretty decent 8.8-mB AVI. A little banding in some light-blue transition areas, but not bad at all for what you get. I used the 1-pass method.]
It may be more of a matter of how good your original files are. You (ideally) should not be capturing the video using any kind of compression at all.