I'd suggest taking inspiration from real world international relations theories for inspiration. Don't want to get into a lenghty description of what they are (for those interested the following suggestions are based on theories of Kenneth Waltz and Alexander Wendt), but would like to focus instead into how they can be translated into the game:
-A diplomatic system making distinction on basis of relative power between nations. Make a distinction between regular states, powers (regional top power and its equal(s) if any are present ) and superpowers (galactic top power and its equal(s) if any are present). The status of being one of these should alter diplomacy towards them, a small state might have no business dealing with a far away regional power, but always is interested in relations with galactic superpower. Superpowers should pretty much always have at least a rivalry if not outright animosity and so on.
-Being a superpower should provide added ability to influence those of lesser status (more willing to accept trades, increased value of trust from the smaller AI) BUT come with the drawback that your every action is judged by the rest of the galaxy in a harsher light. Purges and slavery by superpowers should elicit strong negative reaction from just about everyone, whereas a small stellar empire doing it should go practically unnoticed. This will additionally go a long way to solve the harsh purge penalty problem mentioned in other threads.
-AI personalities should be expanded somewhat to create affinities towards different behavior on the international (galactic?) arena. States don't just compete but are also capable of cooperation and promotion of shared goals, but this behavior isn't a fixed constant but depends both on the "personality" and "values" of a given state as much as the practical situation around it. A state stuck among a group of brutal barbaric expansionist empires might be pacifistic by ideology but will have to adopt similiar less scrupulous attitudes as a means of preserving its existence at least until the threat is neutralized, even if it doesn't identify with militaristic values. And similiarly a brutal despotic empire stuck in the middle of a bunch of harmonious cooperative space nations that are willing to perform humanitarian intervention ought to at least temporarily behave in a more agreeable way. In short it makes no sense to be space Gandhi when surround by space Huns and it makes no sense to be space Genghis when an alliance of friendly empires would knock you out right away. The ability for the AI to shift between these behaviors (even if very unwillingly) would add a sense of dynamic and rational behavior. A third in between behavior could serve as the default way the AI acts now, warring others but mostly for material gain and treating other empires as competition rather than enemies.
While I understand this would likely be no easy feat to translate to a game, something of the sort would go a long way to helping diplomacy become more dynamic and making it feel like you're dealing with real space nations following their own interest. Since Stellaris is heavily based on a combination of real world politics mixed with sci-fi and gameplay conventions and because I know Paradox loves to try to push the genre towards a great balance of complexity and fun gameplay, I have confidence they could be able to implement more real world concepts and make them reasonably fun to play.
