If I follow what you're doing, you are starting out with your color space as Adobe RGB 1998, right? Forget "Save for Web" for a minute and try this: What you have to do (and sizing has nothing to do with this) when you save an image for the web, is do a Mode/Convert to Profile, and make sure the DESTINATION space is sRGB. (The Source space should say Adobe 1998). Do the conversion, save it as a JPG (be careful not to overwrite the original file) and put it on the web somewhere. Actually, you can just open a browser and do File/Open, and select that image, to see the same thing. As I said, re-sizing has nothing to do with it, neither does any other manipulation, JPG setting, file size, etc. The problem is, browsers are NOT color managed - they don't know how to display Adobe 1998. A program like PS/CS knows how to read color in any mode, Internet Explorer and Firefox do not, so you have to give them the lowest common denominator in color space, which is sRGB. Here are a couple samples of images that started out as Adobe 1998, which I mode-converted to sRGB. I think you can see the difference.
By the way, I never got in the habit of using "Save for Web" so I'm not sure if it does the mode change or not, but when I just tried it, I think not, so that would explain why its been no help on your problem.
Regards,
Andy Pearlman
Andy Pearlman Studio