Alex, I took your image, set it to the pixel size you gave of 1990x4212 at a resolution of 300. The image I downloaded was smaller and I wanted to use the dimensions you had. I then selected all of the black areas of the map with the wand tool, inverted the selection, smoothed it by 3 pixels, and painted a the selection green on yet another layer. I used a large round brush (just the basic photoshop round brush) set to 771 pixels to paint this region of the map. This size probably does not matter all that much, I just wanted a large brush.
I've attached the full-sized file. As you can see, at 100% magnification the coasts are smoothish but as you zoom in it gets a bit more jagged as one would expect.