I use Snapfish, Webshots, and Photobucket. All are free and do a good job. I can't get to Photobucket at work anymore, so I've resorted to using the other two. Both work similarly and it doesn't seem to make much difference which one I use.
I use Imageevent It cost like 25 bucks per year. But you can upload videos and a bunch of different types of files up to I think like 100 MB. You can store up to 1500 files.
SmugMug.. different levels of service, but mine is $25 a year. They go up to a professional service where you can protect and sell your pictures right through their site.
No more 'Red x's' when linking to the pictures online!