lol I couldn't help myself but play around with how one might continue the map with just crisp lines. Click image for larger version. 

Name:	World-Valgard viking screwing around.jpg 
Views:	151 
Size:	1.58 MB 
ID:	56453

I get what you mean art deco and mythic feeling. It's a kind of neat combination and I'm not going to lie I'm not even sure what to suggest unfortunately. It is indeed odd to think of occupants before the living space that would form them first but whatever works :p

I guess maybe if I wanted a more mythic feel I'd go the hand painted route for everything.