Digging out of a hole is hard, I agree. For example, Trung Trac is -90 hostile towards me in my current game. Her agenda is to dislike a leader who has more commander promotions -- which I do. And I intend to get more, on both army and fleet commanders. Don't know how to fix that.
I have an interesting challenge in this game with Jose Rizal. He was my buddy, even ally, in Antiquity. He was leading me in legacy points at the end of Antiquity, getting his first Treasure Fleet before me. I arranged to backstab him like this. He was actually allied with Trung (who hates me). I moved my troops near Jose's cities, then declared a formal war on Trung. Jose stuck by his ally and declared on me. I snatched up his island city and assaulted one of his big cities. Couldn't quite take it, due to his knights counterattack.
After the war, I'd like to patch things up, but Jose has LOTS of negative modifiers. I'm starting endeavours with other leaders, especially those in Distant Lands. But it is going to take a LONG time to erase the negatives.
Other leader agendas are harder to comply with. Isabella cares about Natural Wonders. Can't do a lot with that. Catherine will dislike me more and more, as I accumulate relics.