I second Zenfolio.
If you are only looking for a hosting site, Zenfolio offers 1 GB of storage for $25.00 / year. They increase your storage by 1GB for every year you subscribe, so on year 2 you get 2 GB, on year 3 you get 3 GB etc.
They have a mid level plan at $40 / year. Be sure you read everything if you plan on using this plan. They offer unlimited storage on this plan. The confusing thing on the mid-level plan is that they offer the ability to sell your photos through a third party provider, but only at cost. It's a little confusing and I don't understand why they do this. It is a blemish on an otherwise great service.
The pro plan is $100. Unlimited storage, ability to sell at a profit through MPIx or self fulfillment if you are masochistic. Lots of premade site templates or you can make your own. Embeddable flideshows. For less than $10/month, you really can't beat the service.