Re-encode to approx 43% the original bitrate. You probably also want to resize down, although it isn't a required step.
You never mentioned the input video format. At a guess I would be going with an avi with VBR mp3 audio. So try VirtualDubMod or mencoder.