You could use ownCloud. It has a web UI where you can access and manage your files (and contacts, calendars, plus more), so it would fit your basic requirements software-side. If you don't want to self-host (which would be a good option here), there are several providers offering you their services. While some of them are located within the "Five Eyes" (e.g. UK), there are also several outside that (at a quick glance, I see e.g. 3 of them with free plans residing in Germany).
So how would ownCloud match your requirements?
- Free: Yes. The software itself is free, and there are "free plans" available if you cannot self-host.
- Files hosted outside "Five Eyes": As pointed out, that can be arranged.
- Should work with Linux and Windows: Access is possible cross-platform. There are native clients for most platforms, but ownCloud's Web interface definitely guarantees that for all relevant platforms.
- Data in Motion and at Rest encryption: That depends on your configuration. ownCloud itself offers encrypted storage, but of course the setup is depending on the provider. You can, however, encrypt files before uploading them (and decrypt them after download) to have full control over that.
Note: There's a recent fork of ownCloud which is said to be more community-oriented: Nextcloud. For now, it's 100% compatible with ownCloud. And the same way, there are providers already using that – again including candidates outside the "Five Eyes". In the list, they are found easily by the corresponding countries' flags. Take your pick!