Depèn de la qualitat que estiguis disposat a sacrificar. Per la relació qualitat/mida m'agrada el codec DivX, crec que duu un "bitrate calculator" que et permet calcular quins paràmetres de qualitat has de posar per aconseguir una mida determinada. Per cert que també s'ha de prestar atenció a la compressió del sò, de vegades representa una part important de la mida del vídeo.
Per fer la conversió te recoman el Virtualdub. A més de la compressió d'audio i vídeo, pots aplicar un filtre que redueixi la ressolució, p.ex. de 640x480 a 320x240.
Finalment, diuen que la màxima qualitat s'aconsegueix fent la compressió en 2 passades, tot i que jo no ho he provat. Si creus que perd massa qualitat amb els paràmetres que provis, una opció seria provar amb 2 passades per veure si millora (la mida hauria de ser la mateixa), però no tenc experiència en aquest mètode.