I did something I've been very daunted and nervous about doing because I could never get it right for years which frustrated me. However, I tried it again in Photoshop today and the results came out much better than I expected.

Tools I Used
-Paintbrush (draw the state outlines; also to color the ocean from scratch)
-Eyedropper Tool
-Smudge Tool (Blend in some of the pixel areas from low resolution)
-Duplicated the states part of the map (one is blurred; 50% opacity, the other left as is)
-Added Contrast (maxed out at -150%) and slight brightness (2%)
-Sharpened the black state outlines
-Multiple Layers!
and I think that's it, listing everything from memory.
Take a look...(attachments below)