The programs listed here are provided as exhibitions of just how compressed a Linux ELF executable can be and still accomplish something useful. Because they are potentially useful, they all adhere to the ELF specification (though most of them still bypass libc in favor of making direct system calls).
In order to use one of these programs, you can download the assembler source and build it with nasm. If you don't want to install nasm, and you have reason to believe that I can be trusted, you can download a pre-built binary and run it directly. (Note that you will need to use chmod +x to mark a downloaded binary as executable.)
This is your classic hexdump program. I wrote it one day in a fit of pique, after trying (and failing) to convince the standard Linux programs to output bytes in the formatting style that I've been accustomed to since before reaching my majority. I still use this program on a regular basis, even though xxd(1) can now produce nearly identical output. My original version simply read from standard input, but I quickly found this irritating enough that I sacrificed a few more bytes in order to allow it to accept a filename on the command line.
This is a simple base64 decoder utility. Like hexdump, it can either accept a filename on the command line, or work on standard input. Since sometimes very large files are encoded in base64, I allowed the program to be slightly larger than strictly necessary in order to optimize for speed. This version is actually noticeably faster than the utility included in GNU coreutils for 32-bit Linux.
This utility was my attempt to tackle an important yet complex tool. ls is one of those programs that you really can't do without, in part because its functionality has almost no overlap with other standard tools, but also because it's tailored to provide multiple pieces of information at a glance. My version is missing a few standard features, such as sorting, but it does recognize many commonly-used command-line options, such as -l, -a, -F, and -R. The "long" output format only displays numeric user IDs, timestamps are displayed as ages instead of actual times, and the columnar output is not particularly clever. But beyond these things, it conforms pretty closely to the standard ls program we all know and love.
This is an implementation of the standard Unix utility. It displays the prime factors of the integers provided on the command line, or on standard input if no arguments are given. Instead of simply trying to achieve the smallest possible size, I decided to shoot for real portability with this program, for a change. It not only conforms to the requirements of the ELF specification, it also avoids making direct system calls and instead dynamically links with libc. It should continue to work with any future version of Linux, as long as new versions of the libc ABI and the ELF specification remain backwards-compatible. It also includes online help, version information, and error messages, and therefore arguably stands as a completely functional replacement for the standard utility in GNU coreutils. Because factoring huge prime numbers can sometimes run for a long time, I attempted to optimize for speed and size both. This program makes significant use of the FPU in order to increase parallelization in the inner loop. (Back when I first wrote it, it was significantly faster than the standard GNU program. Since then, the coreutils program has been updated with some advanced mathematics, and it's now the faster program.)
By now you may be thinking: "These program are technically useful, I suppose, but isn't there anything interesting in here?" Well, how about a game? This is an implementation of Snake, a classic computer game — in fact it's so old that you can hardly find it anymore in its original form. I originally wrote this as an Easter Egg for a contract involving text-terminal interfaces. Now it's available to all as a tiny program. In case you've never played it, the object of the game is to guide your snake around the playing field, eating the food blocks that appear at random locations, and dodging the walls and your own tail. As you eat the blocks, your score increases but so does your length. The program should work on any modern terminal (though see the comments at the top of the source code if your terminal has trouble with the VT100 line-drawing escape sequences). Its small size makes it the perfect addition to a rescue disk! After all, when you've just lost all your data, what's better than a game to distract you from your troubles? (By the way, my personal all-time high score is 478. Can you beat that?)
As a sort of oversized finale to this list, puzzle is a game that runs under X. You've probably seen a 15-16 sliding tile puzzle at some point in your life. Some of you may even remember the program that came with the original 1984 Macintosh operating system. But are you aware that, in order to justify including the puzzle in the limited memory and disk space available, the author squeezed its size down to 600 bytes? (See here for the details.) Alas, while I would have loved to be able to present a Linux binary that matched that size, the ELF structures required to link to all of the required X functions alone needed well over 600 bytes, before I included any assembly code or pixel data. Maybe someone more knowledgeable about X programming than I could reduce the number of functions needed, but for now here's my oversized version. It uses the exact same graphics as the original (which unfortunately means that the window is only slightly larger than its own title bar on a modern display). Lacking access to a Macintosh emulator, I had to rely on my own 25-year-old memory of the program's behavior, so I may have gotten some details wrong. But it is fully functional. And despite all this hedging about its hugeness, at less than 1700 bytes I'd wager that it's still the smallest X program you've ever used.