Good question, I'm currently struggling with this myself at the moment so I hope some good answers will be posted. My personal view on this: I think one of the important questions you'll have to ask yourself is not only how much space you'll be needing in terms of storage, but also how much traffic you're expecting and what growth rate.
If it's a personal/group photo collection (like your holiday pictures, for example) that you and a handful of people will sometimes visit, the traffic won't be too high and the growth will be overseeable. A fixed hosting plan will do, and I'd advice you to take your entire website and switch to another host, not host your site at provider x and your files at provider y.
On the other end of the spectrum, if it's an open-to-everyone image sharing website with viral potential (like the icanhascheeseburger network) you're definitely going to need a flexible hosting plan that's not only prepared for growth over time (multiple dataplans, high bandwidth and storage limits) but also for huge spikes in visitors (the slashdot effect).
For the latter cloud storage may be a really good idea. While the visits and storage is relatively low you pay low prices, albeit higher compared to 'fixed' hosting plans. As your site grows rapidly the storage + costs will automatically grow with you and in time will become cheaper compared to fixed hosting plans, but also save you the trouble of having to upgrade hosting plans or even having downtimes because of high traffic spikes. In this case, stick with a good host for the website and put your images in the cloud.
Make sure your website host can not only handle the requests in terms of bandwidth but also in terms of CPU power. Especially shared hosting can give you a lot of trouble if the website you host takes up too much processor power (like siteground.com, who promise unlimited bandwidth and storage but even with 6 small wordpress blogs I'm hitting my cpu limit almost daily.. this sucks! try to avoid it).
I wish I could back this up for you with some cool statistics but I've yet to find that out myself. In my case it's the second of the stated cases (viral-like image sharing site), but I'm not sure how many visitors to expect and at what growth rate, so I'm sticking to fixed hosting plans until I'm coming close to 75% of storage/bandwidth used. I do think I'll be switching to Amazon S3 hosting very soon, I'll let you know if there's progress.