I explored a bit of the fjords before doing Maxos Temple, but returned after getting to level 16, so I wasn't too over-levelled for the area (the end boss being level 15).
For the area you can teleport to after Maxos Temple, I got to level 22 before proceeding. That was as high a level as I could get to with the opponents and quests still left, and I made sure I earned enough experience to just reach level 22. The reason is a minor spoiler.
The first encounter on Sentinel Island you can mindread to get enough experience to go up a level; being as high a level as possible and just after levelling, and then mindreading anyone who is left, will maximize the experience points received.
