The Airship

Initially, the defeat of the Emperor is cause for celebration, but the party is soon soured when the Dark Knight declares himself as the new Emperor. To further complicate things, he is revealed to be Leon, Maria's brother and (briefly) a former party member. He awaits you in Castle Palamecia, but the party has no way to enter since it is situated in the middle of a mountain range.

You're going to need an airship, and the only man who has one is Cid. Unfortunately, Cid's usual hangout in Poft was obliterated by the Cyclone. Go speak to Paul in Fynn and you'll find Cid as well. With his dying breath, he bequeaths the airship to you. Unfortunately, it's all the way back near Poft. You'll have to make that trek one last time, dealing with post-Cyclone Fynn Area Monsters the whole way. The good news is, once you board the airship, you never have to worry about World Map Random Encounters again! Unfortunatley, unlike in most games in the series, the airship doesn't really open up any new locations (aside from Castle Palamecia).

The World Map

While you're under no obligation to fight any new Random Encounters on the World Map, I would be remiss if I didn't at least mention that they exist. The least interesting of these is the Area Northwest of Fynn, which has the same encounters as the Fynn Area, but assigned different probabilities. Aside these areas, all the new encounter tables are new and nasty. If you want to test your mettle and level up your skills, the World Map is now an effective place to do that. (You may want to wait until the final change in party composition, though.)

The Castle Palamecia Area has a strong desert theme. You'll see a lot of Scissorjaws, tougher versions of Antlions. They are statistically pretty weak despite being rank 6. They sometimes appear with Death Flowers, which you've seen before. The next-most-common Monster in the area is the Sand Worm, who have 7 powerful attacks and an all-party Earthquake 10 attack. While they have 1,290 HP, they have relatively low Defense and Magic Resistance, so Status Ailment Spells (including KO Spells) are potentially effective. Sand Worms are occasionally found alongside Malboros Terra.

The rarest encounter in the area is against an Imperial Shadow, which is essentially a tougher, Undead version of the Emperor. It has 8 powerful attacks that inflict Curse, good Defense, and 3,000 HP. Unlike all other Undead, it is not weak to Fire. Fire isn't resisted either, but Flare and Holy are probably better options. The Blood Sword isn't an option either, as it will backfire on the wielder. To add insult to injury, Imperial Shadows don't even drop anything. The Kashuan Keep Area has the same encounters as the Castle Palamecia Area, Imperial Shadow included, but with a different distribution.

The Mysidia Area is where you will find the toughest encounters on the World Map. You'll most frequently fight Salamanders, basically the Fire variant of Ice Lizards. They're a bit tougher overall, and use Blaze 16 rather than Icestorm 16, but their weakness to Ice is easily exploited. The Pit Fiends they usually appear with are a different story. They are thankfully less annoying than the Imps they share a sprite with, though they can use Fire 16 and Stun 16. Neither Ice nor Fire are effective, but with 750 HP and low Defense, they aren't difficult to defeat. They can appear in groups without Salamanders as well.

The most annoying new Monster in the area is the Mega Parasite. Their six attacks are weak and cause Amnesia, which will likely not do anything except prevent a front-line fighter from gaining stats at the end of combat. They can use Drain 16, but the thing you don't want to see is Osmose 16. If they drain all of one of your casters' MP pools, you won't be able to use Osmose or Swap to restore them, and will need to use an Ether or Elixir.

Some of the rarer Monsters in the area can be quite dangerous. The Mantis Kings that appear alongside Killer Mantises aren't much of a problem (Ice is effective]), but Hecteyes can be a dangerous foe. They resist or absorb every Element and frequently use Osmose and other annoying spells. Physical attacks are effective due to their moderate Defense, but they still have 1,140 HP to go through and can appear in groups as large as 5. Non-Elemental Spells are also effective.

Finally, there are the rare Great Malboros, which are a serious threat to any front-line Character with insufficient Evasion. Their eight attacks cause every temporary Status Ailment at once, leaving the victim virtually powerless. Basuna 5 can suffice to cure them, but you may be better off having your mages pound the Great Malboros with their moist powerful Spells.

There is an Area east of Mysidia with similar encounters to the Mysidia Area. Great Malboros are more common, and the rare encounter combines them with dangerous Abyss Worms. These things get 8 powerful attacks, but can also wear down the party with the non-resistible Cyclone 13. They have no specific weaknesses, but physical attacks and (non-Fire) Spells can chip through their 1,290 HP.