I think the background for the legend will have to be some sort of tanny, parchmenty color with lettering done in a color similar to the lines of the drawing. Also, a border of alternating strokes of black and tan like on the map itself. Ideally the legend would be an "unpainted" area to start with and then decorated, but not as much as the cartouche.