[elcapitan]

> It turned out the medinas (old towns) themselves were so densly packed, that you could not see much of the sky to get any lock on satellites, and the internet coverage was very spotty.

Instead of a paper map I usually use Openstreetmap (OsmAnd client) for that - you download the map beforehand, and then just read it like a paper map in case you have no satellite. Switch on landmarks etc for recognising places better. It also has much more footways and small streets than google maps.