Aside: Tzen and Maranda

Your immediate destination is Vector, but there are two other occupied towns on the southern continent. While there's no plot necessity to visiting them, they do offer some background and a few upgrades. The Exp. and AP gained by traversing the countryside can be helpful in preparing for the MagiTek Research Facility as well. Tzen is to the north, while Maranda is to the west and south. Tzen is closer, so if you plan to visit both towns, I recommend starting there.

Tzen

To reach Tzen, head north past Vector, bearing east as you pass the city. One bit of information here is in relation to the Guardian, which you are warned to run from if you should encounter it. (This is good advice.) You'll also learn a bit more about the Imperial Base, which is supposedly guarding a gate of some kind.

The Weapon Shop features the Boomerang, the most powerful Weapon available for Locke so far. If you do buy one (instead of, for example, sticking with the effects of the ThiefKnife), put Locke in the back row to take full advantage of it. The only new armor in the Armor Shop is the Mithril Helm, which offers marginally better Defense than the Green Beret but lacks the bonus to maximum HP. It's cheaper at 2,000 GP, but you shouldn't need to skimp at this point.

The Relic Shop features only Relics you've seen before, but two of them had never been available for purchase to this point. The constant Haste effect of the RunningShoes is always useful, and worth the steep asking price of 7,000 GP. Another Black Belt or two may also be worth buying, depending on your party makeup and just how much you want to justify weapon purchases for Characters that always use special abilities.

The Item Shop sells the usual array of Items, so there's not much else to do here once you've talked to everyone and upgraded your gear. If you want to have a quick, stress-free trip to Maranda (or Vector), search the forest area just east of Tzen to find a Chocobo Stable.

Maranda

To reach Maranda from Tzen, you can follow the western coastline south. From Albrook, you'll want to stay south of Vector as you head west through a mountain pass, then turn south when you see the western shore. It's a long walk either way, so renting a chocobo near Tzen is the safest route, albeit not the most rewarding one. There's even less information here than in Tzen, and Maranda doesn't even have any place to buy Items or Relics, but they do sell a few things you may want.

The Boomerang is available for sale in the Weapon Shop, as in Tzen. There is another new item available here, the Trident. You can buy one for Edgar, but the Epee is more powerful and he's unlikely to use either anyway. It is Water-Elemental, which works well against the machines in the MagiTek Factory, but the Drill and Chain Saw are still better.

Similarly, Maranda offers the same new piece of Armor that was available in Tzen (the Mithril Helm) as well as a nice new piece, the Mithril Mail. This is a significant upgrade over the Armor you've seen before, at least in terms of Defense and Mag.Def. It's a no-brainer upgrade for anyone wearing a Mithril Vest, but the decision to give up the bonuses offered by the White Dress or Ninja Gear is tougher. I'd recommend the upgrade for anyone in the front row. Locke will gain more from the Speed boost than the defenses if he's in the back throwing a Boomerang.

When you're done shopping, it's time to move on to Vector. As with Tzen, Maranda has a convenient Chocobo Stable nearby. This one is in located deep within the forest to the east of town, in the narrow part near the southeastern boundary. You will be able to rest in Vector, so you don't necessarily need to avoid combat when heading there.

Even More Aside: The Imperial Base

There is even less reason to visit the Imperial Base than Tzen or Maranda, but if you want to check it out at this point, head east from Albrook. At the end of a narrow mountain pass on the other side of the desert, you'll find this Base in front of a bridge into what appears to be a sheer mountain face.

You'll notice a variety of soldiers wandering the area, all of whom will attack if you speak to them. Walking soldiers (whether brown or green) turn out to be groups of four Commandos, while armored soldiers are a Mega Armor paired with a ProtoArmor. Even if you win a fight, you'll be kicked out of the base. Neither encounter is needed for the Veldt (the Commandos can be fought in Vector and the armor encounter doesn't appear there at all), and while they do yield reasonable Exp. and GP, the AP rewards are abysmal. The 4 Commandos Encounter yields only a single AP, and the Mega Armor, ProtoArmor Encounter doesn't grant any AP at all! There is a treasure room here, but it's locked with no way in. Long story short, there's not a whole lot of interest here right now.