I believe it is Leo at Crassus Harbor. I picked it up in this order:
- Original spice quest where you broker the deal;
- Talked to a person (again at Crassus Harbor) who gives you information about the side effects of Spice;
- After this there is a quest where you are asked to collect things for a Earth Museum
The third quest is the quest that unlocked the black market terminals for me. I can tell you, I just ended up going along with what the quest giver asked of me at every level, then asked to be paid in spice. I have no idea if other decisions affect whether or not the black market terminals are unlocked or no.