I would not suggest using save for web or the web photo gallery for two reasons, number one it removes metadata from the images, and if you are a professional that should be plenty of reason. Number two is quality, if you want a quality image why would you want to let someone else tell you how to lower the size of YOUR images.
What are the pixel dimention requirements for the image? How small do you want/need the images?
Part of your problem might be that you are starting with a CMYK image....WHY?? I routinely deliver CMYK images to clients(mostly designers/printers) but I NEVER EVER EVER convert to CMYK until I am COMPLETELY finished with the image. Why limit yourself to such a small color space??
One other tip for higher quality images, when reducing the size of images by going to image, image size, use bicubic smoother, and you can also try reducing your images in steps, like 10% at a time. If all of your images are the same size all the time(an maybe even your web size) just make yourself an action...The computer will do it in 1/10th of the time it would take you! Why not make Photoshop work for you not you work in Photoshop?
Please post a few images so we can look at them. I will gladly do the same so you can see what I do. Can you post a high res so I can get a crack at it? What version of Photoshop are you using? What are your color management settings? Have you ever looked at them (not to be rude, but alot of people, yes even professionals, have never looked at them and do not know what they mean or do...this BLOWS MY MIND!!)
DBX
(Try it my way, it might work...)