I wanted to report back on this. I was able to get better much better results by using PNG's only. PNG's are lossless, so the compression level does not affect the quality.
I scaled my images in PhotoShop to the exact pixel size as I am using for my full size images, so they do not get resized even when the watermark is added. (I verified this by bringing the images back into photoshop to compare to the original)
The Thumbnails DO loose sharpness compared to the same image resized in PhotoShop. I mitigated this somewhat by cropping in closer, and over-sharpening the original before import. This is due to limitations in GD, the resizing module that is default in PHP. This is a known issue that I found numerous references to. There is a better PHP module called ImageMagik, that also offers Sharpening options (at the cost of larger file size). I have used gallery components that give you a choice which method to use, that would be a good edition in the future.