Hi there,
There are many ways to do that and I think the best option in terms of end result's size and quality would be to encode them in DivX.
But, I think Windows Movie Maker can provide you with very good results as well (I assume you have Windows XP, also make sure u have the new version (v2) of Windows Movie Maker which is available for free - Windows Update should offer it for you if you don't already have it.)
Just run Windows Movie Maker from your start menu (or just go to RUN=> type "moviemk" then hit Enter)
Once it's loaded, go to the File menu and click on Import into collections...
Browse to your original file location, click on it and make sure that the check box for "Create Clips for video files" in not checked then click on Import
Soon you'll see a thumbnail of the video file you clicked on. Right Click on the tumbnail and click on Add to Storyboard
Now from the File menu click on Save Movie File...
Click on My Computer then Next
On the next screen Enter the name you desire and the location for the new file to be saved (make sure it's a different name or location from the original) .. Click Next
The window you should be at right now is where you'll have control over the file size and quality. Just make sure you click on "show more choices..." then make your desired choice from all the different options there. This depends on the type of video you have and the desired file size so I'll leave it to you to make the right choice, all the info is on that screen just go over it and make your choice.
Once done, click next and the file will be saved ... after it's done view it and if you don't like it for some reason repeat all the steps but change the qulity or size settings to get a better result.
Ok I hope it works out for you. Good luck.
Ciao for now.