Anri of Astora is a unique character in Dark Souls III whose gender changes depending on the gender of your own character. You’ll first encounter her and Horace at the bonfire near the Road of Sacrifices. Talk to the both of them and exhaust their dialogue, and then proceed to the Cathedral of the Deep and defeat the boss there. After doing so, the pair will show up at Firelink Shrine. Exhaust their dialogue again, and you’ll find Anri in the Catacombs of Carthus next.
In the first area of the Catacombs, before heading down the long flight of steps with the large skeleton ball, head down the steps to the lower area to find Anri. She’ll be looking for Horace. You can find her again in the Catacombs on the ledge next to the rope bridge. To find Horace, simply cut the rope bridge to create a ladder that leads you further down into the Catacombs. You’ll find the Smouldering Lake optional area. From the entrance, hug the right wall until you find an opening. Horace will be here as a hostile NPC. You can either kill him, or go back to tell Anri where he is. If you tell her, she will go down and be killed by Horace, bringing an end to her questline.