Have you gone through Stone's flying fortress yet? I think I entered there about level 26, and went up a couple levels (reaching level 29 in the final fight). Just before then I had finished off Banabus' cave and started using his hammer, and upgraded my other weapon to a hammer as well, so didn't have many problems in Stone's fortress. Raze's flying fortress would be the next easiest (the entrance teleporters for both are in the mountains near the harbor), then probably Broken Valley, Kali's fortress and Keara's fortress.
