I didn't see this when it first went through, but http://www.nearlyfreespeech.net has done well by me—they don't have a fixed monthly fee, you're billed strictly your resource consumption, and at what seem to me to be quite reasonable rates.

Edit: I just went back and did the arithmetic on your storage needs, and they're probably not the best option for you, given those parameters (their storage charge is $10/GB/month). I like them a lot for smaller-scale operations, though.