Sebastian's DLC follows through the story like side quests, you'll need to do those before you finish an act (He has one "main" quest per act)
The Black Emporium is there to stay forever, but I'd check it at the start and end of each act.
I would save Legacy and Mark of the Assassin before you start "The Last Straw" so the weapons there would match your level instead of doing both quests in Act 1 and having useless armor and weapons for the rest of the game. Hawke's Key is worth it.
As for which order, you have no control over Sebastian's, but it doesn't matter which order you do Legacy or Mark of the Assasin in. Just choose what you think feels right.