You're experiencing dithering due to the color reduction of the GIF color table. Gif images can only contain a maximum of 256 colors. There's really not a great deal you can do about it.
You are asking the gif format to support smooth color, which it doesn't. The best you can do is experiment with the dithering options in the Save for Web window. However, you are never going to get a smooth color photograph when using the gif format.