So, you touched on the confidentiality corner of the CIA Triad which is very important and you bring to mind the question of whether of not we can trust VPN service providers to ensure it.

Perhaps, open source VPN software would be a good idea. If there is transparency with the code, I doubt we would have to worry about anybody trying to sneak in a backdoor.

On the topic of data storage, there are blockchain projects that intend to answer that but scaling is an issue. I am most familiar with SiaCoin and the idea is you have data distributed across up to 21 hosts and the data can ONLY be accessed with your private key. Also, due to the distributed nature of the data, I believe it is fault tolerant as long as 7 of those 21 stay online.

I currently accept the risk of using OneDrive which was bundled with MS Office but I may consider giving renting from the SiaCoin network a try. It's still not a fully mature project but David Vorick and team have high ambitions. Looking forward to seeing it develop.