Many executables that you use on a day-to-day basis on your desktop system have many options that you will rarely need and could either spare completely or substitute with a generic command. Going through the executables you designated for your minimum system and stripping out options, error messages and built-in help is an easy way of reducing such files.
Also, consider compile-time options, as they also influence size. On desktop systems this isn't a big deal, so often the Makefiles will provide the safest options, not the most efficient with respect to size. As a general way to reduce size, don't include the default libs, but explicitly include the libs you need. To do so, use the -nostdlib and -nostartfiles flags with gcc, and include libc with -lc explicitly along with any other libs your app needs.