queda un poco grande el ejecutable pero si que es muy posible , lo que debes tener en cuenta es que al generar el ejecutable , solo te genere el exe y no esas formas de pasarlo a exe que tienes muchos otros archivos.

debes ver un poco las siguientes modulos:

sockets
subprocess(con este podras enviar y recibir comandos de consola)
httplib (con este podras descargar otros archivos de la web , y enviar peticiones a una web y muchisimo mas xD)


_winreg(asi te agregas al registro de windows para que inicie con el sistema o muchas otras cosas)

para interfaz grafica si que tienes muchas opciones en lo personal me gusta wxpython pero tambien esta qt para python tkinter etc etc

ya si deseas puedes mezclarlo con c  y tener algo muy bueno