>>13
gcc tends to produce many redundant data on windows executables.
I can easily make 1-3kb executables on Windows using MSVC, this is done by disabling debug information, dynamically linking MSVCRT(or similar), and linking with a fairly low file alignment (lowest safest portable value possible was about 0x400). This results in a small and clean PE header, a .text section containing just the necesarry code, an .rdata section if any static immutable constants are present (usually contains at least the Import Address Table, and the Import Table), and a .data section for defined and undefined non-const data. This makes puts it at about ~3KB, for a minimal functional executable. It can be made much tinier by abusing the PE format, but one shouldn't expect the compiler to do that for you: you either write your own tools for this, or create the file manually or will have to play more tricks with your linker.
I do believe gcc is capable of doing such things, but I haven't tried it myself. Sadly, most gcc compiled exes in win32 I've seen were somewhat bloated, but that doesn't convience me that it's not doable, as a good deal of win32 executables compiled using msvc are fat as well because people don't know or care enough to make them tiny.
If size is of such great importance, one of the many tiny PE packers can be used to reduce the size by quite a bit, there's some packers which generate under 1KB executables with ease (as long as the code/data is that compressible/tiny).