Journey South
Upon leaving Narshe, you'll find yourself on the World Map for the first time. Random encounters are always present on the World Map, and each region has its own set. Further, you'll find different sets of encounters on plains, in forests, and in deserts. In the Narshe Area, you'll find only Leafers and Dark Winds, though they will appear in greater numbers in forests than on the plains. Neither is a threat, and they can be taken out easily with normal attacks, or Terra can take out entire groups with Fire. Locke can steal Tonics from both.
For the moment you want to head south and west until you reach a sprawling desert. Two new enemies inhabit this desert, the Sand Ray and the Areneid. Neither is vulnerable to Fire, and both have a good amount of HP but low Defense, so normal attacks are your best bet.
Figaro Castle
Your destination is Figaro Castle, which is located in the middle of the desert. You can look for the white dot on the minimap to pinpoint its exact location. Locke is recognized at the door, and guards block most paths except the one directly to the Throne Room, so head there first. (If you do go exploring, just make sure you don't buy an AutoCrossbow since you're about to get one for free.) Before speaking to King Edgar, have Terra Cure Locke to full if he's low on HP. When you do speak to Edgar, you will get a chance to name him. Afterwards, Locke will leave for the moment and you can explore the castle fully with Terra.
There are no monsters in Figaro Castle, but you have an even more dastardly opponent to grapple with: event triggers! You can wander around the castle for quite some time without anything happening if you don't talk to the right people. The "right people" in this case means the matron in the West Tower. Upon speaking to her, you will see a cutscene and get to name Edgar's brother Sabin. Once this is done, you can return to the throne room and speak to Edgar again to advance the plot.
But first things first! There are two shops and four treasure chests to check out in your immediate vicinity. The West Shop sells items and contains a Soft, while the East Shop sells tools for Edgar and contains both a Tonic and an Antidote ripe for the taking. You already have an AutoCrossbow, but the NoiseBlaster and Bio Blaster are worth picking up. There is one more treasure chest in the upper hall north of the Throne Room, which contains a Fenix Down. The West Wing contains a free inn which will only heal Terra right now, but will be handy later.
Upon returning to speak to Edgar, Kefka, an agent of the Empire, will arrive. You've received some mixed signals about Figaro's relationship with the Empire from the guards in the castle, so you might expect this to go badly. And you'd be right! You'll be in control of Edgar, and have to speak to Kefka's two guards before Kefka himself will respond. You'll switch back to Terra, who is asked to follow Locke to the East Tower.
After Terra goes to bed, a long (and in my opinion, great) scene will play out. After you're done speaking with Kefka and his cronies, speak to the guard at the entrance to the Middle Hall. This will eventually lead to an encounter with 2 M-TekArmors against your full complement of party members. The enemy will get an automatic back attack, so use the Row command for anyone intending to use normal attacks (e.g., Locke). For a fun aside, have Terra cast a spell on one of the M-TekArmors during this fight. The M-TekArmors are tough to kill and you don't have any particular weaknesses you can exploit, but Edgar's tools will prove to be very effective. The AutoCrossbow does a lot of damage, and the NoiseBlaster can inflict Muddled on your foes. (The Bio Blaster is not a good choice here because M-TekArmors are immune to the Poison status.)
Once the battle is won, you'll find yourself riding a chocobo. Take Edgar's advice and head southeast toward the South Figaro Cave.