Fixed my own problem, I believe. When I do this:
gcc foo.o -s -fno-exceptions -fno-rtti -ofoo
I get much smaller code than before. Got the info from here:
http://www.spacejack.org/games/mingw/
Edit: Okay, so that was a general command that wouldn't work in real life. Here's a better example or two:
g++ foo.cc -s -fno-exceptions -fno-rtti -ofoo
gcc foo.c -s -fno-exceptions -ofoo