Reduce size of compiled binary

Hey /prog/, I'm making a remote control tool that works over Tor  because reasons.
But Tor itself weights 3Mio and my final executable is over 1Mio upx'd.
I'm compiling in plain C with Visual'12, have activated all the size optimisation but it's not enough. The client must be able to transfer itself over the network very fast and fit even on small embeded systems.

So do you know of any methods to reduce size further, or any packer better than UPX ? I don't care if it makes my code really slow, but size is critical.

>>6
I can't afford Asm sadly, I don't have the time to rewrite everything, gcc|msvc will have to do.
I need to run on small embedded systems, often x86 linux, so I can't link with msvcrt or use windows-specific apis like WaitFor*Object.
I'll look at CyaSSL and miniz, but "stripping out the fluff" implies rewriting tor and netcode to use light libs, possibly bringing tons of new security issues.

>>3
I have bad experience with --fomit-frame-pointer, gcc used to break my OS during stack switchs, had to use dirty tricks.
Is it worth the 4Bytes/function saved ?