For full folder backups, duplicity [1] has been great for me, does incremental backups, and has quite a few backends. You control rotation policies, full-snapshot frequency, etc, and bring your own storage (works with s3, rsync, etc.). Full-folder recovery is also pretty easy in my experience.
The downside is that it's all on you to configure providers, pay for storage, and I'm not aware of any indexing or ability to retrieve single files. Also, it's CLI-based, so it might not be very intuitive for desktop use. Still, a free solution with lots of utility. :-)
The issue with these for me is that with the common cloud storage providers, even just backing up my Documents folder raises it above the price of BackBlaze or a similar offering.
Duplicity can backup to Backblaze's B2 service, which is an S3-alike where you only pay for storage and download, not upload. 40$ to restore backup in the case of a failed disk, and a few bucks a month (literally) for storage.
I use rsync [1] to backup my laptop to my server twice an hour. (Hard-linking files that already exist in previous images.) Then another script [2] on the server prunes old backups every night.
Anyone can recommend if a good backup alternative that works on a Linux (desktop)?