I also noticed what Rol just said when I played ACIV. Whenever I discovered an area I saw everything what there is to do and completed that one by one. That has nothing to do with exploration and discovery.
As for Zelda I can only say that I climbed the first tower and it's nothing but a lookout. You still need to mark suspicious spots that you want to check out yourself.