Do you want cheap or do you want free? There are plenty of free web hosting sites around. I don't know which are the good and which are the bad. I have used in the past Geocities, but it is a pain with an ad banner on the side. I currently use Freewebs just for a little photo gallery thing.
As for creating a gallery thing, I also have that free. It's called Simple Viewer (google) and it is very simple. I have mine parsing my photobucket site for the images and it works just fine. It is flash based, and I normally despise flash sites because they are usually very slow. This one is very simple in just having thumbnail images on the side and a viewing image center/other side. You can see my example
here. I think there are scripts you can download and make it easier to create, but I edit the pages by hand to add photo content. If you want to parse your photobucket account, there is a site to grab the code and it does it all automatically. I don't do that as I enter file/shot info, thus I enter everything by hand, as I said.
As for web size photos? I despise when people upload more than 800px on the long side in landscape. All my photos are done in 800x533 landscape and 480x600 portrait orientation so that they fit on nearly anyone's screen.
I also save all my photos at quality 8 in Photoshop for the web so that the file sizes are generally less than 200 kb. I find that more than 250kb takes too long to load in my opinion. If someone shows me their gallery to view and I find the photos taking 30 seconds to load each one, I won't be viewing very long. I do have some of the first ones I uploaded that are around 400kb (800x533 @ quality 10-12 in Photoshop) and they are indeed long to load. I still need to rework them to a smaller size. See my gallery linked above and the first half of the images will load pretty quick, but around the 2nd half, they start to slow because of the filesize needing reworked. I have to get busy on that.
There is one feature of the Simple Viewer that I mentioned above that is nice. You can state in the code a maximum display size (limit to 800, 1024, whatever you want) and also, the image displayed will resize automatically to fit the browser window. Thus, if you do limit to a large size for those that have large resolution to view, I can still see it sized right for my lower resolution monitor. The downfall to that is, load times are still dependent on what filesize you've uploaded.
Another free flash gallery creator is Lightroom Galleries 4, completely free download and it creates the same flash galleries that is available to create in Adobe Lightroom. I haven't gotten around to looking at it much. If I could figure out how to parse Photobucket like my Simple Viewer one does, I would look at it closer.