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.

>>11
I'm targeting regular desktop windows, linux and embedded linuxoid systems.
I'm not sure what I would use AppCompactor for. I'm already using UPX when possible, I tried other packers but they all give worse results.

I do have experience in ASM. I made a freaking operating system. Thingy.
But rewriting 3Mo worth of opcodes by hand, and without breaking Tor's anonymity and security, seems a bit unrealistic.

I'll probably have to rewrite tor to use cyassl/miniz anyway, and drop the support for relays and bridges since I only need client functionnality. But I'll do it in plain C.

Also gcc has interesting flags, I'd like to switch to mingw-gcc only instead of msvc, but I can't find a suitable IDE.
Code::blocks is shit with a broken autocompletion and weird bugs, Eclipse is slow and not made for C/C++. There is also QtCreator but it's not made for plain C.