Ok, so here's my work since last night.
Added a background texture layer, I'm attempting the papery watercolor effect. That looks a lot better already though I'm not quite sure it's perfect yet. The border is supposed to be a fancy frame for the map, as some nobleman might have it upholstered. Again, it isn't perfect but it's a start.
There's now an actual line for the journey, which I plan on narrating in the large empty ocean areas. The thought in my mind right now is that the small island nation is populated by a race of halflings who are kind of being beset on all sides by "big folk", and who enterprisingly decide to go off and look for a new land to expand into. I hope the relative sizes of the civilization I added into the 'old world' helps reflect that. I'm also debating using some sort of color banners to denote different nations, but haven't made up my mind yet. Opinions are welcome!