4th floor of Sunken Shrine, probably about 1/30 chance. You have a higher encounter rate in the Temple of Chaos.
When you land to go to Lufenia, walk around the top of the lake. NE part of the desert where the mirage tower is. 1/62 chance of a battle.
Treasure chest in Mt. Gulg where you get the Flame Mail.
In front of the treasure chest on the 4th floor in Terra Cave.
If you walk around on the 5th floor of the Flying Fortress you'll have a 1/64 chance of fighting Warmech. Take 5 steps from the middle of the bridge (where the pillars are) up. You'll either encounter a warmech, 4 fire hydras, or 3 aeros. War mech is the strongest enemy in the game.
Only able to be found on the 4F basement in the Temple of Chaos. You can fight him a lot more often between the two "zig-zag" areas on your way to get the masamune. Around the torch that sets on the wall. I've fought about 8 here.
While in the ship, press and hold "X". Then press "O" till the screen fades away, and a puzzle appears. You can win prizes this time too, yeah! Here's how to beat it: