As stated, you only need to encounter them. So that means attempting their 1st (or only) mission or seeing them in the context of the storyline.
Several of the characters will provide you with more than one mission. All is explained in detail in the Item & Location sticky. In the description it states if the character will only appear at certain times of the day. If nothing is noted, the character can appear anytime. The characters may also not always be in their locations. If the character you are looking for is not where the map states they should be, that is normal. Simply continue on about your business, and try back later, there is no need to post in the forums asking where the character are, and why they haven't appeared. Have some patience, and go enjoy Liberty City!
1. Badman: You will find him sitting on a bench in front of the Pill Pharm after you complete the mission "Shadow." He will ask you to accompany him for a hit on a Russian gang.
2. Brian Part 3: He will be standing on a street corner after you have completed both of his other encounters. He will ask you to protect him as he goes to apologize to some drug dealers.
3. Brian Part 1: You will find him next to Roman's Cab Depot after you complete the mission "It's Your Call." He will hand you $100 as an insult for looking poor.
4. Mel: He will be standing just up the block from your first safehouse after you complete "Escuela of the Streets." He wants you to protect him while he goes to pay back some loan sharks.
5. Brian Part 2: He will be standing near Vlad's bar after you complete his first encounter. He will ask you to take him to his dealer.
6. Ilyena Faustin: She will be standing on the boardwalk after you complete "Escuela of the Streets." She will ask you to deal with her daughter's new boyfriend, just as her late husband had you deal with her last one.
7. Cherise: You will find her at the Cluckin' Bell after you complete "The Holland Play" and "Ruff Rider," provided you kept her alive in Ruff Ryder. She will ask for protection from her new boyfriend.
8. Clarence: You will find him on the street after completing "Holland Nights," provided you decided to spare him in that mission. He will attack you, and you must defend yourself.
9. Jeff Part 1: He will be standing on a street corner after you complete "Photo Shoot." He will ask you to follow his cheating wife and take a picture of her and her man.
10. Jeff Part 2: Jeff will contact you via cell phone after you complete his first encounter, and ask you to meet him at this location, a parking garage. He has killed his wife and needs assistance in disposing of the body.
11. Marnie Part 2: You will find her leaning against a building on a street corner after completing her first encounter. She will ask you to take her to a train station so she can flee the city.
12. Pathos Part 2: This time he will be just down the street from your previous encounter with him, and will spawn once you complete that first encounter. He will again be dealing with some hecklers, this time take them out, then take Pathos to the hospital.
13. Pathos Part 1: He will be near the Thespian Theaters selling his CDs after you complete "Escuela of the Streets." He will ask you to rough up some of his hecklers.
14. Hossan: He will be selling items on a street corner after you complete "The Puerto Rican Connection." He will ask you to accompany him on a few errands to collect money owed to him.
15. Sara Part 1: She will standing in Suffolk during nighttime hours after completing "The Puerto Rican Connection." She will ask you to take her home to make her husband jealous, culminating in a fight with him.
16. Jeff Part 3: You will find him sitting on a sidewalk after completing his second encounter. He will ask you to kill his new wife, when you say no, he will kill himself, end of mission.
17. Marnie Part 1: Marnie will be sitting on a park bench by the large fountain after you complete "Three Leaf Clover." She will ask you to take her to her dealer to get her drugs.
18. Sara Part 2: She will be standing near Pier 45 once you complete her first encounter, even though she won't recognize you. She will ask you to pick up a package at Perseus and bring it back to her.
19. Eddie Low Part 1: He will be at the end of an alley between 10pm and 4am after you complete "Three Leaf Clover." He will ask you to escort him to the docks.
20. Eddie Low Part 2: He will be waiting for you between 10pm and 4am after you finish your first encounter with him. He will attack you, and you will have to eliminate him.
21. Ivan: Provided you kept him alive in "Ivan the Not So Terrible, you will find him on a street corner after completing "Three Leaf Clover." He will ask you to escort him as he collects debts.
22. Gracie: Gracie will be standing in front of her home after you complete "Diamonds Are A Girl's Best Friend." When she sees you she will send her guards to attack you, and you need to defend yourself.