Something simple and straightforward for the border itself is probably best, for obvious reasons. However I am a fan of those early modern maps with all sorts of stuff arranged outside the map itself. A fairly common one seems to have been portraits of "typical" people from various regions on the map, and drawings of major cities along the top. It doesn't distract from the map itself as much as you might think, either. Even something completely over-the-top like Petro Plancio's map has a reasonable example of the two combined, although perhaps the ratio of illustration:map is a bit out. There's a good strong border around the map itself with latitude markings, and then lots of interesting stuff to look at around the edge.