All I can recall is that losing or gaining two provinces = -/+1 influence, and breaking an alliance = -1 influence. I think failed crusades lose you 2 points. The agents thing I'm not sure of, but that's just because I haven't really watched it closely...

I think the change of influence with a new King does depend on his stats, but the precise relationship I'm not sure of. And, yeah, the Byz are fixed, well he IS the Byzantine Emperor after all