Before He Runs: Abu'l Nuqoud
We've already seen plenty of the air to assassinate move. Let's mix things up with a traditional, low profile, stealth kill (and then get right back into the air assassinations 
). Of all the targets which are possible to stealth assassinate, Abu'l Nuqoud is the most difficult to stealth assassinate. You'll earn style points just getting into proper position on this one.
Abu'l Nuqoud is the Merchant King, so I guess that makes him Tamir's boss. He must be doing well for himself as his Palace is about the nicest place you'd ever want to kill someone.
INVESTIGATION
Two of the investigations turn up useful maps of the Merchant King's Palace. The first is the Eavesdropping mission on the north end of town. Sit on the bench at the river's edge halfway between flag #2 and flag #3 on this map. The second is the Informer in the alley below flag #29. He's conveniently located opposite the Palace's main gate. Remember, to view the maps in-game it's Pause, Memory Log, trigger left/right, View Attachment.
One map reveals the locations of the archers on the second floor during a party and the other shows a creative route to get backstage. We're not going to use that route but I've included it in the bonus material at the end of the video. Below is a single map with the information corrected and combined.
From here on out you'll need to do a minimum of three Investigations, so pick one more. (Tip: Eavesdropping is fast and easy.) The other Informer recommends climbing the fountain. What a bonehead.
PREPARATION
Take a tour of the Merchant King's Palace while it's lightly guarded. You may even want to do a dry run of how you will get from the fountain to the stage (see map and HUNT section below). Beware of archers. They're all on the uppermost roof at this time.
Make sure you've done at least three investigations before returning to the Assassin's Bureau and briefing the Rafiq.
APPROACH
There's a small gate in the northwest perimeter wall around the palace. To the left of the two man guard post stands a solo guard in front of a skinny pine tree. Stealth assassinate the solo guard (see red X on map). The dead body distracts the guard post but do not enter the side gate - it's a trap! No, the purpose of this kill is to create a gap in the defense so Altaïr can sneak out after the assassination. We're planning way ahead here. 
It's much easier to enter the Palace through the main gate in the northeast iron fence. Four guards stand across the gate. You have the usual four options: fight, climb, Scholars, or distract. Climbing over the front fence is fast. I use a dead body distraction because, well, I always go for the dead body distraction! Don't bother with these Scholars. They're slow and essentially "guarded" by trouble makers.
Whatever you choose, keep an eye out for the guard patrol inside the perimeter wall. They march back and forth between the left and right side doors of the Palace. Most of the time they're in one of the side yards but once in awhile they cross right behind the four man post.
Once inside the gate, head up the stairs and through the front door which stands ajar. The side doors are wide open but there's a heavier guard presence on the sides and no advantage to entering that way. I believe it's impossible to climb the Palace from the outside, so that lets out a rooftop entry.
MELEE
During the poisoning cutscene, you hear the exterior doors slam shut as archers take their positions all around the second floor. These must be the same archers that usually work roof duty because the upper roof now stands empty.
The stage is flanked by twin minarets. Someone walking offstage would pass through one or the other. The minaret at stage right (note: using theatrical directions, stage right is to Abu'l Nuquod's right as he faces the main courtyard) has a door on the back of it. If Abu'l Naqoud spots Altaïr, this door and the exit door at the rear of the Palace open automatically and Abu'l runs through both.
The minaret at stage left has a door facing the stage. This door opens whenever one of Abu'l Nuqoud's personal bodyguards spots Altaïr. Finally, there's a door along the southeast balcony where the main courtyard meets the secondary courtyard. I've never seen this door open. Whenever you encounter a closed door, it's always possible to climb around or over it.
HUNT
The goal of this walkthrough is to stealth assassinate both of the bodyguards and then Abu'l Nuqoud himself without any of them seeing it coming. For an extra challenge, try to do the whole thing while remaining Anonymous (white icon) and without killing anyone other than the three men onstage.
A good rule of thumb is to keep moving. After Altaïr loiters in one place for 10 seconds or so, he starts to draw archer fire (even if your witness indicator is idle). So move quickly but not recklessly from one phase to the next.
The first problem is getting up to the second floor. There aren't any ladders so you'll have to climb something. There are many places to climb but only a precious few where you can do so completely undetected. Run into the secondary courtyard which is to your left as you face the stage. Hold down the B button (Circle on PlayStation 3) to Tackle your way through the crowd. You may switch to the A button (X on PS3) to Sprint once the crowd thins.
Locate the ceremonial hut that stands in the center of the small courtyard. Don't climb the hut! Instead, move around to the left of it and look for the four black and white striped arches behind the hut (i.e. to the southwest). Climb the column between the first and second arches. There's an archer to your right and two over your left shoulder, but none should notice you. Continue straight ahead, skipping onto the second floor balcony.
Turn right and pass behind the archer. It's not necessary to kill him. As you exit the covered part of the balcony you will be facing a recessed and decorated wall. Climb up and over the railing at the top. You're now on the south side of the middle dome (a Viewpoint). Turn right and circle around the near side of the dome to the stone platform above the stage. (Cheat: If you continue towards the minaret at stage left, both bodyguards will quietly walk offstage. This level is full of glitches like that.)
One bodyguard stands at the left rear of the stage while the other stands front and center. Abu'l saunters back and forth between stage right and center stage. It takes him a full 48 seconds to complete one circuit. You want to strike while he's moving left to right. If Abu'l is anywhere near stage right, wait here until Abu'l touches his bodyguard's shoulder. Altaïr may take an arrow or two to the chest while he waits. That's okay as long as you're up here and not down on the stage.
Here's where things get interesting. While facing the main courtyard (with Abu'l and his bodyguards on the stage below you) leap forward. Altaïr quietly lands on the wooden beam that passes over Abu'l Nuqoud's head. You should be standing on the beam, not hanging beneath it.
Turn 180 degrees and face the rear of the stage. Center yourself so that the alcove is straight ahead and leap for it. You should now be hanging in the center of a doorway. If so, just press the B button (Circle on PS3) to drop onto the stage. If you were slightly off target then you'll find yourself clinging onto the side of an arch. That's okay too. Press B (or Circle) and then hold it to Drop and Grasp the bar below, center yourself, and then press it again. You should now be in the door of the alcove.
ASSASSINATION
Hug the rear wall to sneak up on the bodyguard at stage left. Use a low profile assassination from the rear. Before Altaïr even removes his blade from the guard's neck, use the right thumbstick to turn around and line up your sights on the next bodyguard. You've only got a few seconds to get him before he notices the dead body, so you can use the head start. You don't even have enough time to walk from one bodyguard to the next. Use the Right Trigger (R1 on PS3) to jog a few steps before walking up behind him and doing another stealth assassination.
If your timing was right, Abu'l will be moving towards stage right and will have missed all the action. Move in behind him and complete the trifecta of stealth assassinations.
ESCAPE
There's only one hiding spot on the Palace grounds. Go back to the corpse of the first bodyguard. Climb the decorated wall behind where he had been standing and proceed over the rail onto the roof. To your left is the middle dome. Look for the telltale "leap of faith" plank on your right. Plunge into the hay cart below.
You're still within the perimeter wall here. Wait until the guard patrol turn their backs on the hay cart before emerging. Down the stairs to your right is the small northwest gate but it is still guarded by a two man post. Walk behind them and continue up the stairs (being mindful of the other guard patrol ahead). The first pine tree on the left marks the spot where Altaïr pre-assassinated that guard way back at the beginning. Climb over the wall and you're home free.
CHASE
If anything goes wrong with the assassination (and believe me, there are a ton of things that can go wrong) Abu'l Nuqoud runs out the back door of the Palace. Below is a map of the routes he may take. Abu'l isn't as creative as Talal. He only knows two routes through the Western Sarouja Souk to the guard tower.
Besides chasing him down from behind, there's something else you can do: head him off at the pass. Abu'l takes the longest possible route through the rear courtyard, making a large horseshoe shape. Altaïr is able to take a more direct route. Immediately after passing through the back door, turn 90 degrees to the right and Sprint straight ahead. Continue Sprinting to Free-step across the platforms in the fountain, being careful not to fall in the water. See the dashed red line on the map. The largest platform is the one where you find flag #33. Unfortunately, you'll probably encounter a guard patrol before you see Abu'l. He will be to your left, hanging back and waiting for an opportunity to run past Altaïr.
Note: I took a slightly different route to the stage in the video. However, in no way does this invalidate the information above.