I explored every hex except for one isolated ice hex that I can't reach on a large, continents map. I did this at chieftan level, so there's no AI out there exploring the ocean. I sailed my caravel all the way around the world and then uncovered every ocean hex and then explored every land hex. And... I still did not get the Magellan achievement for circumnavigation.