I would seriously, seriously suggest never using that method unless you are just looking for a quick, no fuss export. Save for Web and Devices is a much more powerful tool.
To start, choosing an image file size that you think is reasonable for the number of images on that page and that allows a reasonable page download speed for your viewers is a must. Do some testing on your own, but I bet you see that even half meg (500KB) images load very quickly. If I remember the file you posted was about 200K, the file digital paradise posted was 550K, why throw away all that detail if it doesnt really impact most viewer? You can either get close to a preferred file size with the first screen, or you can choose the dropdown menu that allows you to optimize for file size you have chosen ... Ps will choose the settings for you.
You also have the ability to preview before and after and even use 4-up to see the effect of different settings on compression. Some images will compress much more easily than others. Always choose baseline optimized.
To back up a little, uploading files to the POTN server can put them through another compression process. It makes it really hard for us to know if we are seeing the same thing you see with the original files. If you can upload them to dropbox we can see the original unaltered files.
PSA: The above post may contain sarcasm, reply at your own risk | Not in gear database: Auto Sears 50mm 2.0 / 3x CL-360, Nikon SB-28, SunPak auto 322 D, Minolta 20