Una opción gratuita puede ser
InfanView. Pero de todas maneras seguramente lo que estás haciendo con el paint es bajarle la calidad. Si en vez del parametro 100% de calidad se lo bajas, seguro consigues menor peso. El paint deja los JPG con bastante baja calidad.
