How big is the file that you're putting out?

That should tell us a lot about it.

I live to use divX or Xvid to encode my videos, because it seems to make them small but still look sharp.

I do it outside of Premire though. In Premire I just output as an uncompressed file, and then I convert it with DivX via Rad Video Tools.