another suggestion is to start shipping binaries. i just looked at your download page and while it's not much of an issue for me to compile it, it may be just enough work to make other people not want to try it. especially when you start talking about header files and dependency versions.

make deb and rpm packages, get it into the freebsd/openbsd/pkgsrc/fink port trees. make your installation page as short as "pkg_add tarsnap" and only link to the compilation instructions for other, less commonly used architectures. (do you have the ability to see what os/arch most of your users are using?)