Sobre Py2Exe, si lo configuras bien, al utilizarlo te deberia dejar tu programa repartido en varios archivos entre los cuales los que vas a notar más a la vista van a ser una DLL que contiene Python en si (creo), ejecutables con los nombres de los archivos .py que tenias (son los que tienen tu codigo, creo) y un archivo .zip que dentro tendra todas las librerias de python.
Los archivos DLL y EXE los podes comprimir con UPX que tiene un ratio de compresión muy alto. Comprimí especialmente el dll q creo que se llamaba python27.dll (python 2.7) porque es el mas pesado.
En cuanto al zip podes poder abrir el archivo y borrarle todas las librerías que no use tu programa.
Ojo de no borrar ciertos archivos que usa python o tendrás que deshacer y eso da flojera
También creo que se podía aumentar la compresión del zip.
Con todo eso te debería quedar algo mas compacto y potable. El tema de las interfaces gráficas le aumenta bastante el peso a los proyectos ya que las librerías gráficas son muy pesadas. WxWidgets es más ligero que GTK y QT pero aun así aumenta bastante el tamaño de archivo.
Tiempo atrás cuando necesitaba una app super ligera usaba TK pero solo para uso personal ya que TK no es una buena opcion que digamos
SI sabes algo de C++ podrías aprender a usar FLTK que es muy ligero y tiene un binding para Python. (En el caso de querer usar algo ligero)
Aun con todo lo que te dije WxWidgets es muy buena opción así que no me hagas caso
Saludos