In terms of pricing, I find Hetzner is best for under 1TB, Backblaze for over 1TB. Both have great documentation for setting up any number of backup methods (SFTP, SSH, Rsync, Rclone, Borg, etc).
Rsync, Rclone, and Borg are all good options and some may be built into your choice of OS if you use a dedicated NAS system. Choose whatever is easiest for you.
The backups are gonna be encrypted in transit regardless of method, and Im pretty sure most backup providers encrypt data on their servers so you dont have to manage that I dont think.
When you commit to backups, IMO you should do them daily - Most backup clients have options for "sync" options which will ignore unchanged files and only upload changes, so a daily backup is not only more up-to-date but also more efficient once the first backup completes.