Paloom
Your destination is Salamand, but you'll pass two different towns on your way there. Cross the lake northeast of Altair to find the first of these towns, Paloom. There is nothing significant here plot-wise at this time, but the shops are filled with nice upgrades you probably can't afford yet. You'll be coming this way back and forth for a while in the early game, so make sure to pick up various upgrades as you can.
The Paloom Area has a number of new encounters for you to deal with. Goblin Guards are the first Monster you'll encounter that can hit characters in the back row, using its Bow 1 attack. Soldiers share this attack, though the encounter with them is quite rare at this point. These are tough enemies with solid defense. Spells are your best bet until you get some increased skill and new Weapons.
There are some excellent new pieces of Armor available in Paloom. You won't find the Bronze Armor in any dungeons, but you will find the other bronze pieces, as well as the Copper Cuirass (which is like the Bronze Armor, but better—and cheaper!). If you can afford it, upgrade any front-line fighters as soon as you can, and get cuirasses for any mages. Their trivial magic penalty makes them a mage's primary source of Defense.
On the weapon side, the new offerings are the Dagger and Mace, more powerful versions of the Knife and Staff, respectively. Note that unlike the Staff, the Mace has a magic penalty of 20%, so it's probably not worth giving to a mage. Some of the mace-type staves later in the game are quite powerful, though, so consider training a front-line fighter in their use.
You will also find three new Spells available in Paloom, each for 400 gil. They are the defensive Spells Blink, Protect, and Shell. Blink and Shell are both vital defensive spells in the long term, though for the moment Minwu can cast them as needed. You'll want them when he's gone, if not before, but the high price tag means you may need to wait a while. Protect is unfortunately bugged, and only works on the caster. There won't be many situations where it's useful as a result, so you may want to save a spell slot for something else.
There is no sanctuary in Paloom, but there is a ship to Poft here which costs 32 gil to ride. Note that the ship remains where you left it last, so if you walk back to the other town, you won't be able to take the ship. The ship is convenient and will allow you to save time and avoid pointless battles, but this early in the game you may be better off fighting your way to Poft to earn money and skills.
Once you've explored Paloom, assuming you didn't take the ferry, you can head northeast along the coast to reach Poft. You'll have to circle around a large bay to reach the second port town, but if you head north past the edge of the mountains and then proceed northwest, you will reach Salamand instead. There's not much of note in Poft at this time, so if you didn't take the ferry you may want to skip it for now.
Poft (Optional)
The town of Poft is disappointingly similar to Paloom, featuring the same shops carrying the same Items and Spells. The ferry between them even has the same cost of 32 gil. The only real point of interest here is the first series appearance of Cid in the pub.
Cid will teach you about his [Airship], and you can even speak to his assistant to ride it to various points on the world map. He can take you directly to your destination of Salamand, but it will cost you a hefty 200 gil. As with the ferry, you may be better off walking in the early game to gain skills and money. Cid can also take you to Bafsk, Semitt Falls, and Kashuan Keep for varying fees. Keep these options in mind as you travel later on in the game.
Because of its slightly out-of-the-way location, Poft's main role is as the base of operations for Cid's airship. Keep in mind that the ferry will remain in whatever town it last sailed to, so if you pass it up on a trip in one direction, it will not be available for the return trip, either. Plan accordingly if you intend to pay for transportation.
To reach Salamand on foot from Poft, head northwest, making sure to pass north of the mountains near the bay. Salamand lies nestled south of a larger mountain range up north. In both the Poft and Salamand Areas you'll find more Soldiers and Goblin Guards than before, as well as the new Queen Bee. These are accompanied by three rows of Hornets, so you can defeat the Queen Bee with Spells before it will be able to attack (which only monsters in the first two surviving ranks can do). You'll want to avoid her attacks, as they can inflict Poison, the permanent version of Venom. If you are afflicted, Minwu's Esuna Spell is your most cost-effective option to remove Poison.