Looks pretty good.
As you pointed out, the fonts are definitely a bit spidery for the resolution of the image, which leads them to appearing fractured and aliased (that includes the settlement labels along the coast). How easy it will be to fix will depend largely on how you've done the map. If you have a tool that's keeping the text in a form that's editable, you might be able to double the resolution of your image, export that to a lossless format, and then reduce the dimensions by half (old-fashioned manual antialiasing). If you can adjust the metrics on your font renderer, you might be able to get it to be less spidery at that resolution. Another option might be to go with a sans serif font rather than the one you have here. They tend to be more readable to smaller sizes.

I find it hard to read the labels in the ocean because the tone of their coloring (especially for gray outlines on the text) is very close to the tone of the ocean.

I do see a little bit of noise in the ocean area and I suspect that the land could benefit from a similar treatment. What is the effect that you're trying to get with the noise? It looks like you're trying to give a result similar to offset printing on mediocre paper like the kind old folks used to have in school. Increasing the resolution fo the piece and adding some structured texture might help (or it might look worse).