Solution: VPS outside Canada to do your downloads from.

But what you describe is a networking problem (transit costs of your ISP passed on to you). Not a storage problem.

A "cloud storage" provider is just going to keep the data you store in a datacenter near to you anyway, not halfway around the world. But it's not like keeping your physical stuff with a storage company. You can easily store the data yourself with many more advantages. The marketing teams for "cloud storage" services will no doubt try to convince people otherwise.