Ok, firstly I'd recommend always that you are in the editing stage, to save the edits as AVI Uncompressed. (sometimes named as "full frames") . Every time you use a non lossless codec, which are the majority, you will apply a quality loss in every save. Similar than is no good (except in some circumstances and with some tools) editing a JPG. (I've done when no other source available, and there's quite a need for it)
You need to know there are two concepts, the format or container (ie, AVI, MOV, etc), and the codec (divx, .h264, intel indeo, etc)
Once you have your final version ready to go (always keep a security backup of this master AVI file) you have several options for a reduce memory size output (not going to list every available possibility, some important ones) :
FLV. If is for web, this is a good option if you are going to use a player in your own server (Flowplayer, and JW Player from LongTail video come to mind as 2 great free server side players)
This, if converted with the cheap and probably best converter for flv called Flex Standard, from ON2.com , will become a really small file.
Also good this format to upload to some place like Viddler, one of the very few places where if you upload the FLV, no loss is applied, they don't modify it if it's an flv.
There are free tools to compile a flv as well, like Riva encoder http://rivavx.com/?encoder , and my favourite in the free land (for Windows) , Mediacoder : http://www.mediacoderhq.com
AVI, MOV, etc using .h264 codec. This is a relatively new option giving extremely small sizes at a great quality. It's possibly the best option. Only problem is that it can be more of a problem for the users to play it depending on their system configuration. Blip.tv does support .h264 codec directly, as far as I know. At youtube, avi with .h264 codec work really great, in my own experience. And as are so small files(probably for some other reason, too), they upload very fast to youtube.
.h264 codec download: http://www.afreecodec.com/26/h264-codec/
(I use ffdshow ones)
AVI with DIVX. This is really spread, large user base. Even home DVDs do support it directly. This won't produce such small files as the above options, but will do them perhaps small enough and tend to have no problems opening in your target users. As with any codec, you need to install divx ( divx.com ). Beware the format won't allow you to ouput any proportion (ratio). IE: good if your video has standard proportions (you have several workarounds for this in the edit stage, but..)
Techsmith codec. This is specially good for screencast, tutorials. Really small files. But you need the target users to have the free techsmith codec installed in their machines. Which is ok if is a controlled target audience, some people which you can tell to install it: generally a bad habit, I prefer to output stuff which won't need additional installs and are problems free. This codec is free for the players, the users, but if want to use it to encode files, you need to install Camtasia, their product. They gave it free 3.x version with several magazines. techsmith.com
Flv (if compiled well, or just using the on2.com product) and mpeg, mov, or avi with .h264 should be able to produce 4 mins videos that you say in 20 megs or so, it all depends on the size(I mean pixels dimensions (ie, 640x480, etc..)) of the video (beware on target machines, not every one can playback an hd video ,for performance), and how much quality is desired to lose.
Edit: You have also a free tool called Virtualdub, at virtualdub.org, which you can use for simple import an uncompressed AVI and output (setting in "video"/"compression" menu which codec you wish) with the format (avi, mpeg, etc) and codec (divx, .h264, etc) which you prefer. Should not be needed having Premiere as you do , but... Thought would not harm to put the link for it as well.