On most Webhosts you really only have to worry about disk space and monthly transfer. While it is technically true that many hosts also have hidden limits on the number of files, you are talking about many more files than you are looking at doing.
To figure it out, take the estimated number of monthly visitors, times the average number of images they view, times the average size of the image, plus 10-20% "fudge factor", and you have a rough idea of your required monthly transfer, which you can compare to the plan of a given Web host.
Note that most shared hosting providers are seriously overselling though, so it will be damn hard to get near the limits, and if you somehow do, they will probably suspend your account for being a resource hog.
If it looks like you are going to push a lot of bandwidth, then I would go VPS or dedicated, because then you will actually have the traffic that you need.
I would advise against using an external photo hosting service - they often shut down images that get too much traffic, or pull other crap.