I think part of the problem is most maps are depicted how humans best use them. Issues to consider...

Have you seen the movie Contact with Jodie Foster? In that movie, the initial alien information sent to Earth could not be read until the scientists realized that the data image was not meant to be read in 2d, in fact 'markers' in the data text itself proved to be overlap points when viewing the content as a three dimensional tube or sphere, instead of flat surface. So our assumption that a map is a top down birds-eye-view of a 2D map might be incomprehensible to an alien mind.

Humans have binocular vision. Many animals like horse or squid have eyes on the opposite sides of their head - what such an animal reads in what it sees cannot be identical to beings of binocular vision. What about 3 eyed aliens, how would they view the world. Maps created for use by these 3 different visual arrangements would be perceived differently by all 3 types. And of course these are just suppositions on 3 ways of viewing the world - there could perhaps be an infinite number of perceptions based on whether a being uses eyes at all.

Like your Piers Anthony reference, you need to decide how your aliens perceive the world around them and go from there to cartographic composition.

This concept could be so complicated that our feeble, binocular-based vision mind-set can't effectively conceive. Pick a point of view and then 'wing it' to base the science behind it and go from there...