It's no cloud but I've used rsync.net as an offsite backup. Unlimited bandwith and you just pay for storage with discounts for volume. Cheapest they show is $0.32/GB/mo.

All though for 3TB that would come out to roughly $983/mo a far cry from your wanted $500/yr.

The problem with co-locating a NAS is that you have to also support it.