I always use the gcc option -Os, which turns off all optimisations that increase code size... Don't know how much it will help, but there's no harm in trying ;)
Just a nitpick, but that's not completely true. -Os will keep the optimizations -O2 perform _but_ which do not increase the code size too much. Furthermore, it adds some optimizations to reduce code size.
There have been reports of programs (or even the Linux kernel) running faster with -Os then -O2 due to the small code size (which can eventually fit inside the CPU cache).
If you are really interested in this, have a look at this discussion: http://marc.theaimsgroup.com/?l=linux-kernel&m=104457390406050&w=2
But, yes, Simon could try to compile with -Os. Nonetheless, a 1.6 MiB dillo binary (stripped) is very odd. (Heck, I've just tried to compile with -O0 and I got a 329KiB binary).
Maybe a GCC bug? Which version are you using?
Maybe it was statically linked with something that is usually dynamically linked? John.