So here's an update any case anyone happens upon my thread looking for a good online backup service.
I ended up going with IDrive. They just started offering unlimited mobile backup for up to 5 devices. $4.99/year.
Their Android app lets you backup and Restore contacts, photos, videos, calendars, texts, apps, and documents (including .doc, .pdf, .zip and more) with a single tap. And they're compatible with iOS so I can back up my Apple and Android devices into the same account.
https://www.idrive.com/mobile/
I looked into their encryption and they do 256-bit AES with private key so no one but me can access my data. So far I like the interface and I love the price.