The best deal I've found so far is Amazon EBS mounted on a spot priced micro EC2, which is about $55 / month in total for 500GB.
Given the cost of raw HDD storage, I'm sure I can do a lot better than this.
What good alternatives do others use?
NB1: I have OSX and Linux servers to backup
NB2: Backblaze would be awesome, but it doesn't support Linux or have an API yet.