Du kannst versuchen, gcc mit dem Flag -O* aufzurufen, wobei * eine Zahl ist. -O3 sollte schon etwas Kleineres hervorbringen, kompiliert aber auch länger.
Es könnte auch eine gute Idee sein, die Binary nach dem Kompilieren mit strip zu bearbeiten.
Ich habe mal "Hello World" vier mal kompiliert und teilweise gestript. Hier die Ergebnisse (Anm: Unter Linux, deshalb sind die Binaries von Anfang an kleiner)BTW, erstellt MSVC überhaupt komplett lauffähige Binaries? AFAIK verlassen die sich stark auf eine C-Runtime, die mit Windows kommt. Das könnte ein Grund sein, warum sie so klein sind...
BTW2, UPX ist auch ein brauchbarer Packer für Binaries.