Tarsnap: easier to set up and use Duplicity: fully open source, and I think the restore speed was significantly faster ... but I've not properly benchmarked it apples-to-apples.

If you are backing up a lot of frequently changing files (eg. database backups) then tarsnap's bandwidth charges (probably caused by the underlying EC2 charges) can swamp the storage cost. Running duplicity against rsync.net avoids this.

You can host your own backups if you want (supports ftp, sftp, ... check the docs: http://duplicity.nongnu.org/duplicity.1.html), but Tarsnap is an hosted solution.