Definitely the island full of Yans (the one closest to the center of the four continents IIRC). They also happen to be the hardest random encounter in the game and capable of killing you with ease if you don't dispatch them quickly. Odin can come in handy tho if you have him.