Looks really nice! I like this modern style, though I have no idea how to make it myself One suggestion: I'd move the Atlantic Ocean label to sit southeast of Horse Island and curve upwards, and also lower the opacity of it – that'd group the islands together into one focal point, rather than split it into two, and the lower opacity would make it instantly obvious that it's about the sea and not one if the islands.

As to the legend, do you have any ideas for a border around the map? If so, you could just put a white/yellow/anything box in the upper left corner and copy the border to sit around it. Or don't make a cartouche at all – just write directly on the ocean. Maybe put some swirls around the text afterwards, again to group it together.