After paying Gladys 8,000 Bits to recover Udom’s seal - the Official Seal of Halcyon Holding Board - talk to him and he should give you the Byzantium Navkey and some Byzantium Travel Authorization Papers, which entitle you to land at Adjutant Akande’s Landing Pad. Return to the Unreliable and interact with the Navigation Terminal, then travel to "Adjutant Akande’s Landing Pad" on Terra 2.
As you go to leave your ship you’ll find Ellie waiting for you, who apparently has something she needs to say. Apparently she was born in Byzantium, and wants to visit her parents… and for some reason she wants you to come along, and she doesn’t exactly want you to make a great first impression. In fact, she wants you to make a right boor of yourself. This starts the quest The Low Crusade, which you can see to any time you’re willing to take Ellie along with you to Byzantium.
Meeting with Adjutant Akande
Exit the Unreliable on Byzantium and note that, while you’re in Byzantium, you’re not technically in Byzantium yet. There are two landing pads for Byzantium, with Adjutant Akande’s Landing Pad taking you more or less directly to the HHC Building - the corporate heart of Byzantium. On the other hand if you came here (usually much later - after Monarch, at least) by siding with Phineas you’d land at the Byzantium Freight Port Landing Pad and have to work your way to getting access to the bowels of the HHC Building via the quest The City and the Stars, something you can obviously bypass by completing Balance Due. The plus side of going from the Freighter Port Landing Pad is that it takes you through the actual city, complete with all sorts of quests and shops, while Adjutant Akande’s Landing Pad puts you in a less busy part of Byzantium. You can still reach the city proper, but you’ll need to veer off the beaten path a bit, something which will be discussed after your meeting with Adjutant Akande
Make your way west off the landing pad and go through a doorway to reach the HHC Building, stopping at a checkpoint so one Guard Esparza can check your papers. Continue west when she’s done and go through another door between two corporate troopers (a quick look at these guys in TTD should convince you that it’s probably not in your best interest to pick a fight) to reach a room with two vending machines. Peruse them if you wish, then head up an elevator to the south.
When the elevator arrives you’ll find yourself on the third floor of the HHC, the northern end of which is dominated by the desk of Percival Platt, whom you need to chat with. First, however, note two locked doors on the western end of the level. One is simply difficult to open [Lockpick 100] while the other requires the Minster’s HHC Access Card, which you’d otherwise obtain via the quest The City and the Stars - something you have no need to worry about, since you’ve completed Balance Due. There’s also an elevator to the south of Platt’s desk, which will take you down to the first floor of the HHC Building, giving you access to Byzantium.
Anywho, talk to Platt and say what you wish to get in contact with Sophia Akande… remotely, anyways. Listen to her flex her intel on you and she’ll eventually get to the point - you need to earn her trust before she’ll enter into a proper working relationship with you, and to do that she wants you to "retire" one of the Boards cartographers, Rachel Lockwood. Deal with her and then you can move onto the Welles issue. This starts the quest The Demolished Woman and finishes The Puppet Masters, which you’ll get to shortly.
First, however, you’ve got all of Byzantium at your disposal, and as the biggest, most populated city in Halcyon, there’s naturally plenty to see and do here. This naturally calls for a proper "Exploring Byzantium" section to help you locate all the quests and other points of interest in the area, so read on if you care to, otherwise skip ahead to The Demolished Woman.
Note: Working for the Board will make Felix progressively more agitated, and you can expect him to question you after nearly every Board-related quest, including The Puppet Masters. In this case, he only cares to warn you that working with corporations generally ends poorly. The kid’s not wrong.
First you’ll need to get out of the HHC Building, which is easy enough. From Platt’s desk head south and ride an elevator down to reach the first floor, then head north through a security checkpoint. If you were following the Welles path, you’d have had to do some work to get in here, but coming the other way, you’ll have no problems. Just keep going north to reach a door leading to Byzantium’s Acropolis District.
From the HHC Building note that to the northwest lies the Ministry of Accuracy and Morale building, which you can’t access yet, while to the southeast you’ll find an elevator leading down to the Maintenance Tunnels - quests will take you there soon enough, so don’t bother with it yet.
Make your way northeast past a security checkpoint (another problem for those who followed Phineas’ path) and head down some stairs to reach the Estates District. This is where some proper exploration begins, and note that there’s a bunch of loot strewn about, some stealing, some not. Basically almost anything not in a bin is fine to pick up, otherwise you’ll need to be sneaky - this loot will largely be left up to you to get, as you feel fit. Anyways, on to the points of interest.
– North of the stairs leading to the Acropolis District you’ll find the Fenhill Estate, where you’ll need to take Ellie for the quest The Low Crusade.
– Follow the road southeast and you’ll find a woman named Hortense Ingalsbee, who seems dreadfully concerned about Byzantium being infested with people of improper station… including you. Talk to her and after enduring some obnoxious chatter with her ask "What’s wrong with more people coming to Byzantium?" to get her whining about early retirees to find out what this is really all about. Agree to help her to start the quest Why Call Them Back From Retirement?.
– Keep going southeast and you’ll find Minister Clarke’s residence, which is guarded by some corporate troopers. You won’t necessarily know what this place is, of course, but you can trick the information out of a guard with a [Persuade 25] check. This place is really only relevant if you’re following the Phineas path. Don’t go wandering around the yard to the side, as it’s a restricted area.
– From the stairs leading to the Acropolis District, continue northeast under an arch, across a bridge to reach the Prosperity Plaza District, if not the actual plaza itself. From the far side of this bridge turn southeast and head down some stairs, past a man arguing with a vending machine, and turn left (northeast) at a tunnel to find the elevator to the maintenance tunnels, near which is one Giles Molina. Offer to look for his sprats and to start the quest Cupid of the Laboratory.
– Near the elevator to the maintenance tunnels you can also find a door leading to the back area of the Halcyon Parcel Service building - HPS for short. Again, if you were here later during the quest The City and the Stars, you might find this building useful, but working for the Board, the only reason to bother is to loot the room beyond the locked door [Lockpick 60], which houses some loose loot and a few bins.
– From the maintenance tunnels, head southwest to return to the walkway near the canal, then turn southeast, pass through a tunnel, then head up some stairs to the left (northeast) to reach Billingsly’s House of Inebriation. Talk to Mr. Billingsly inside and you can bribe him (at a whopping 7,877 Bits) to get him to tell you where Rachel Lockwood - your target for the quest The Demolished Woman - can be found. Of course, you don’t need that information given this guide… or at all, at that price. If you want any actual service at the bar, however, you’ll need to talk to the Bartender Mechanical.
– Also in Billingsly’s House of Inebriation you’ll find Guard Mayfield, who is quite proud of his new job as one of Minister Clarke’s bodyguards. Pressing him for information will cause him to reveal that he doesn’t really know much about Clarke, but he does have a key to Clarke’s estate. If you pour three bottles of Spectrum Vodka down his throat (you’ll need Ellie in your party, or you’ll need to pass a [Persuade 40] or [Medical 40] check to get him to drink a third time), he’ll get sick, head to an adjacent room, and die. Oops. But you can loot him for his Minster’s Estate Key, bypassing the locked door at the back of the estate [Lockpick 60]. Between this and the UDL Identity Cartridge you can find in the maintenance tunnels, it should make getting into Minister Clarke’s estate a breeze… not that you have any reason to do so on this questline, mind you.
– From the stairs to Billingsly’s House of Inebriation, continue southeast along the canal until you find two corporate troopers talking. Search under the bench one is sitting on to find another UDL Identity Cartridge. They probably shouldn’t just leave these things out in the open…
– Backtrack to the bridge leading to the Estates District and from there head down the stairs to the northeast. To your left (northwest) you’ll find Odeon Pictures, inside of which you’ll find Maverick Johnston, who will offer you an audition, starting the quest At Central. If you don’t meet him here, you’ll find him standing at a four-way intersection northeast of the orrery, just northeast of the actual Prosperity Plaza map marker.
– Continue down the street to the northeast from Odeon Pictures, and at the fork turn southeast, continuing past the front door to the Halcyon Parcel Service building. Continue southeast until you find a fork to the northeast and, at the street corner you’ll find the Bureau of Exploration building. Inside you can talk to Sherman Bradshaw, who can help you (quite unintentionally) advance the quest The Demolished Woman, and once past the lobby you can talk to Alonzo Vallejos to start the task All Halcyon in a Day.
– Exit the Bureau of Exploration building and continue down the street to the southeast until you find some stairs to the right (southwest) leading to the front entrance to Billingsly’s House of Inebriation, which, of course, you’ve no need to enter again. Instead continue southeast along the raised walkway to find Jolicoeur’s Haberdashery and talk to Celeste Jolicoeur the store’s proprietor. She seems oddly enamored with you, and if you wade through her fawning compliments she’ll offer to make an outfit worthy of you… if you can find the right materials. This starts the task Makes Space Suits, Won’t Travel. You can also buy armor and clothing from her, some of which can be difficult to find otherwise, but none of which is technically a rare/unique item.
– Leave Jolicoeur’s Haberdashery and head down two flights of stairs, first southwest, then northeast, to find yourself standing, finally, in Prosperity Plaza itself, right in front of the orrery. Turn northwest and jump over some fences, then search the southwestern wall to find a Poster you can snatch to decorate your ship with.
– Finally search the northeastern end of the plaza to find the Forsythe Luxury Munitions shop, run by Winston Forsythe. Naturally you can buy a variety of weapons and weapon mods from him, including the unique weapons The Exterminator and Pink Slip, should you have an absurd amount of cash to burn.
And that’s it for Byzantium! Picking up these quests won’t hurt, and honestly in the case of Makes Space Suits, Won’t Travel, getting it early will likely reduce backtracking, provided you advance it before you head to Monarch, a nuisance that can’t be avoided if you followed the Phineas path to Byzantium. Complete what you can, as you will, and when ready continue on with The Demolished Woman.