Thanks, great feedback, actually I started reading Melendez article yesterday. I like that idea of placing "breadcrumbs" here and there in between the points of interest.
So here's my layout, the big circles show the areas where the player has to go, or eventually discover, by following the POIs , one is a hill with a temple on top, then is a "weird" rock structure that leads to a beach, and the third is a forest area, the player starts at the center in what is intended to be the "desert". Right now it looks flat, but maybe adding some big dunes or hills to occlude the view towards the rock structure, could work (I'm gonna try that).
The terrain doesn't have to be flat, I just thought that being flat could help accentuate the POIs. And yes ideally the player will go back to that area at least 3 times, each time she goes to the big circles.