To add immersion, make the map look like an 18th century map. Also, allow for the player location to be updated daily, at noon, as that is when they would take their readings with their sextant. Also, (see my other suggestion), make navigation a skill you can level that will result in faster OS time and more exact positioning on the map.