Well actually, I just got it even smaller, perhaps at the cost of performance. The idea is to make a squashfs of the resulting filesystem... and loop-mount it underneath a writable layer using AuFS. After installing what I wanted, I ended up with a 185MB image, which was totally unacceptable. Using the default squashfs options (gzip everything), I got it down to a neat 54MB. Strangely, sequential reading from a loop-mounted squashfs is actually a lot faster than reading directly from ext4fs, and I guess that's because compression cuts down on disk access; random access, on the other hand, is about the same speed. Squashfs also has a non-compressed option, which still managed to shave 30MB off the disk usage, probably because the meta-data use less space.
I ended up using Debian for my project because it's lighter-weight and does the job. The good thing about multistrap (compared to, say, debootstrap) is that it piggybacks on the host's apt, so installing apt (and dependencies) into the guest is optional. All packages can be determined at build-time, so there's no need to chroot into the guest afterwards and install more.
