These areas, in order of increasing difficulty, are the easiest to discover in my opinion:
- Krailos
- Feirist
- Carlin
- Ab'dendriel
- Thais
- Oramond
- Liberty Bay
- Darashia
- Roshamuul
- Gray island
The ones I think are the hardest (I quitted while trying) are: Venore and Port Hope
Some places are hard to reach, or have hard creatures, so make sure to wear and have the necessary equipment for each respawn.
I always start discovering the corners of the map, because in my opinion most of the points of interest appears in the near area you are walking. Others are usually always in the same spots, like the towers in Thais, the chess room, etc