I did start another game, and I seem to have found a work-around. After getting the Byzantium navkey, I talked to Ellie before going to Byzantium. More specifically, I was on Scylla working on Friendship’s Due. I asked her about Zora and Sanjar cooperating, and she segued to talking about her parents. At the end of the conversation, the quest initiated without failing immediately, and it’s currently listed as an active companion quest, so I think it’s working for me now. It might be because of the new game file, I don’t know, but I’m just glad it’s not my entire game that’s bugged.