You should look at Borg for the remote backup software. It does automatic deduplication; has the security posture you're asking for ("untrusted server")*; and is agnostic about which backup cloud provider you use it with. Of course it's FOSS.
I had the same type of thing happen to me with the LastPass leak, which made me very wary of closed-source supposed-e2e encrypted services.
Looking at Borg, it doesn't seem to have native support for the actual transfer of the remote backup. It seems like if I used Borg it would be for a local backup, and then I would need an additional layer to sync the backup to remote storage.
It looks like rclone does, mentioned in other comments here, any others?
In conjunction with Borg, look at InterServer[1] for a VPS.
They provide some of the best cost-per-GiB storage. I've been using them for 3 years, and I prepay a year in advance. I've been super happy. They're cheap; maybe they'll suffer data loss, but I practice the 3-2-1 backup strategy[2]; if they lose data, I have a local backup; if by some weird chance both InterServer goes down and my house burns down at the same time, I've got another backup drive at my parents' house.
If you're more risk-averse, there's rsync.net[3], but it is substantially more expensive. However, it has really good data backup practices on its side.
https://en.wikipedia.org/wiki/Borg_(backup_software)
https://news.ycombinator.com/item?id=21642364 ("BorgBackup: Deduplicating Archiver", 103 comments)
https://news.ycombinator.com/item?id=34152369 ("BorgBackup: Deduplicating archiver with compression and encryption", 177 comments)
*You definitely don't want your private filenames leaked to data brokers, like Backblaze's clients experienced.
https://news.ycombinator.com/item?id=26536019 ("Backblaze submitting names and sizes of files in B2 buckets to Facebook", 517 comments)