The Lady of Grace (Main Quest)
This quest becomes available immediately after completing No Honor Among Thieves. Snag a boat and follow your marker toward an auction site, on an island west of Thebes.
A little prudent recon as you draw close will show hostiles already at the site.
They aren't lying in wait for you specfically, though- they're just searching the area. Use the bushes and fences to dispose of them by stealth, or just snipe them where they stand.
When they're down, enter the area to begin an investigation. Start with the apple-half on the podium, and follow the trail of yellow markers west.
After investigating the bodies, the blood trail, another body on the wharf, and the wharf itself, Bayek will have enough to reconstruct the scene.
Follow your ratiocination westward, to the Temple of Hatshepsut.
Hawksense will show your objective to be on the northside of the main causeway, one level down from the top.
A good angle of attack is to come in from the pyramid on the south side. There are no hostiles in this area, and you can use the scaffolding here to easily reach the building at the top of the causeway.
The roof here makes great sniper nest, if you want to thin local resistance a bit. Do that, and trap the brazier, then look north for a flight of stairs leading down.
Take those stairs, then hang a right at the bottom. This will lead to a small room with some cages, including the caged merchant you need to speak with.
Bust in and question him to get your next clue. Follow your marker southwest to the Set-Ma'at cemetery, where Senu can mark the fugitive's location.
He's being menaced by two thugs, but they're so involved in shouting at the cave that they're easy game for assassination.
Once they're dead, work clockwise around the mastaba to find an entry crack (searching for clues will also reveal it).
Follow the passage to Irsu's nephew, who will yield the relic to you in a cutscene, and reveal the location of Nefertiti's tomb.
Exit through the broken panel, then the scarab wall to get back outside (very near the local Vulture Lair).
Then, follow your marker to the Valley of the Kings, and Nefertiti's tomb.
Enter the tomb and follow the passage, but do not bust open the cracked wall yet- that leads to King Tut's tomb.
Instead, continue on to Nefertiti's sarcophagus, and through the narrow glowing doorway beyond.
This leads to a bridge between life and death, where you will fight some jackal people. They fight pretty much like all the other people you've encountered, so standard tactics apply.
Once you get past them, you emerge in the Afterlife of Aaru.
It's highly recommended that you check out the nearby crater of Nut's Gift- it's stuffed with enough starmetal shards for two upgrades. Likewise, be sure to snipe any giant scorpions you pass in your travels- they're good for two starshards apiece.
When ready, continue this quest by heading the temple in the center of the realm- the Palace of the Lady of Grace.
The place is crawling with jackalmen - kill or evade them, and follow your marker to the centralish portico, just east of the water.
Entering this area allows you to highlight and speak to three priests. Each will give you a different quest as part of appeasing Nefertiti.
Despite your piety and kindess, Nefertiti shows up and goes straight for your throat. She's a quick, dodgy fighter, but if anything is a little less dodgy than her Shadows. Midrange weapons like swords and sickles do well here, through you might switch to double blades when your overpower meter is full.
Also note that Nefertiti seems reluctant to break the tall urns here- you can use them as temporary checks on her attacks.
Defeating Nefertiti lays her to rest, triggers an enigmatic cutscene, and completes the mission. You also earn the queen's Venomous Grace dual blades.