So turns out the main quest needs me to talk to them.

They hate me because I did a Mafia quest that involved killing some of them so now the quest is currently stuck.

Where is the Mediator NPC for them?

Sadly he isn't.

Turns out there's a random guy in a cave and only a side-quest I missed (finding medicine for someone which you can only find by walking inside one of the houses in the city.) is apparently the only part of the game that leads you to him as far as I can find,

Yes, his location is also roughly described in the guide included with the patch but weirdly enough the name is almost the same!