So it sounds like a couple things are going on here: First, you changed from 16 bit to 8 bit color. This reduces the color pallet from 65,536 colors to 256 colors. Once you go to 8 bit, you can go back to 16 bit, but all the original depth is lost and it just stretches 256 colors to 65,536. It's like taking a 10" image, shrinking it to 1", and then blowing it back up to 10" so it's really pixelated.
Second, it sounds like there are some color space conversion issues. I don't know enough about color spaces to help you out, but I would suggest playing with them.
Third, JPEG is generally (standardly) a lossy file format, and I do not believe it supports anything greater than 12 bit, but almost no software (including web browsers) will render JPEGs at anything greater than 8 bit. You can save lossless JPEGs, but again, if you're going from 16 -> 8 bits, you've already lost a lot of information. I do not know the specifics of "Save for Web" options and what it does to the compression, but somehow it manages to usually decrease a file size by about 70% (in my experience), even when set on quality of 100, when compared with normal Photoshop saving of JPEGs at quality of 12. So there is some sort of compression going on there, and I would guess that it's lossy (otherwise, why would it take up less room at "full" quality?).