This should start with a caveat, that transcoding between lossy media formats will generally involve loss of quality.
There are lots of options here:
Convert older formats (
DivX 3 etc) to newer and more efficient codecs (eg
theora) which will generally mostly preserve video/audio quality in a smaller output.
Reduce the target bitrate or target output size, improving size at the cost of reproduction quality.
Reduce the video dimensions, allowing similar reproduction quality at lower total size.
Unless you have strong reasons for another choice,
x264 for video and
aac for audio in an
mp4 container is a good choice for quality and reasonably wide compatibility (but you should encode something short and try it on anything you'll want to play it on - getting widely playable transcoded results remains an exercise in witchcraft).
I find the current command serves me fairly well for converting older formats:
avconv -y -i INPUT -pre:v libx264-slower -b:a 96k -c:v libx264 -c:a libvo_aacenc OUTPUT.mp4
You can scale down the image size by adding
-vf scale=iw*0.5:ih*0.5 before the output name, or set a video bitrate
-b:v, or play with multi-pass options... but mostly the above will produce a reasonable outcome.