I agree. If you're using Premiere to export the final video and you want small file sizes, then take a look at the Adobe Movie Encoder (File > Adobe Media Encoder or there abouts). I believe this is only availbe from Premiere Pro 1.0.
The speed of encoding issue is more related to the power of your PC rather than the codec used in encoding. Put simply, the faster the CPU, the faster the encoding times.
Quality wise, there's inevitably a trade-off between small file sizes and good quality. Lets take away the computer geek language for a second: if you painted a picture with only 3 colours, used the back of a postage stamp as a canvas and then blew this up to A4, quality would be pretty awful, right? If, on the other hand, you use a full size canvass with all the paints you need, quality would be perfect (assuming your name is Monet).
However, some people are better at painting with a limited number of colours by mixing paints. Essentially, you could combine the three colours to make just about any colour you need!
This analogy is how codecs work. Rather than using ALL the data to produce the video, they borrow bits from the previous and preceeding frames. If bits are roughly the same, they just say, "use the data from the previous frame and discard what's in the present". That way, the amount of data is reduced. As there's less data, the file sizes are smaller.
Some codecs are better at compressing the data than others. For example MPEG4 (divx, xvid, wmv etc) is better at making file sizes smaller than MPEG2 without a proportionate decrease in quality.
So, for any given data rate, the quality of MPEG4 would be better. This, of course, has a limit an upper limit. At very high bitrates, there will be no difference between the two. Because of the way they work, the highest quality is used by using a less lossy codec (one that throws less data away at any given datarate), so for those that demand the highest quality, high file sizes are inneviatble.
I think I've strayed from your original question!!! | 
Linear Mode
