After a lot of research and reading, I'm pretty much sold on CrashPlan.
I'm currently in the process of uploading my /home partition (only 1.9 days to go!) as part of their free trial. (Kudos to them for not putting any cap or limit -- you can try it out as much as you want.) I had heard reports of issues with their upload/download speed, but it's all going as smooth as butter over here. Once I've run a successful restore dry-run, I'll be another happy customer.
My only non-encryption-related issue so far is that there doesn't seem to be an easy way to remove a single file (or folder) that has already been deleted. (Being deleted, it no longer shows up in the File Selection list, and therefore cannot be deselected.) Of course, with the lack of any quota, this is not that much of an issue, but it's still bugging me a bit.
(My thanks to Nelson Minar for his tips on increasing the inotify limit and turning off inbound backups.)