Basically, I ended up using duplicity [1], which can back up to a mounted filesystem, WebDAV, ftp, ssh, or S3. It handles encryption and incremental backups, and compresses everything on the backup medium (in encrypted 5M archives, with a seprate index file). This is why I used it; davfs2 is very slow at creating files, and my homedir is mostly very small files. I intially tried rdiff-backup, but it was just way too slow creating all those files. Duplicity, however, is nice-n-fast; 1G of data compressed down to 85 5M files and the initial backup only took a half an hour (plus an hour or so for davfs2 to sync the data up to the server; damn slow DSL...). The incremental backup is also quick, usually only a few megs of data transfer and it takes about a minute to run.
Anyway, I don't see much reason to pay someone else to do this for you. Get duplicity, get an S3 account, and enjoy.
[1] http://duplicity.nongnu.org/
Now it's time to rsync up my music collection. I have 50G of storage to burn through, and the 200M full backup of my homedir just isn't doing it :)