I like the idea of expanding the diplomacy tree with the ideas presented here. Currently the diplomacy tree; as many have said is too short, and does not really give you the flavor of diplomacy.
As suemperincomitatatus suggeste allow a player to persue a racial affinity - i.e. spiders and then unlock new spider related units.
As werewindlefr suggested add a intelligence network tree that allows players to build intelligence related buildings, execute intelligence relate activities, recruit spies (that you can send into enemy empires) and get intelligence reports.
Example:
a. Intelligence Network Tree
1: Intelligence Network - build intelligence HQ; allows recruitment of Spy Champions. Spy Recruitment allows you to recruit champions that can be recruited by other lords, once recruited they update your intelligence report on that kingdom periodicially - starting every 20 turns. This can be reduced to 10 turns with further research.
2. Covert Communications - updates spy report every 15 turns
3. Improved Covert Communications - Updates spy report every 10 turns
4. Counter Intelligence - build Counter Intelligence HQ Building; allows player increased chance to uncover enemy spies and prevent sabatoge or assassination operations. Each building you build increases the chance of detecting enemy spies or assasins that enter this city.
5. Assasins School - Where Assassins are recruited Assasins can be sent into an enemy city to slay an enemy champion or lord. Assasination attacks are resolved on the tactical map.
6. Royal Guard - This technology gives the lord access to additional guard units in the event of an assasintation attempt. Assassinations are resolved on the tactical map.
Example: Player A builds the Assassins school and builds an Assassin. This unit appears as a champion unit the enemy cannot communicate with. The Assassin enters a city and can target any 1) random champion or 2) enemy lord present in that city or 3) do nothing. If enemy lord is selected the Assassin and the Enemy Lord face off on the tactical map. If the enemy lord has researched Royal Guard he is accompanied by d4 champions (or guards if no champions in that tile). If not he faces the assassin alone.
7. Expert Assasins - An improved assasins building can be built. Expert assasins of this school appear as champions that can be recruited to the enemy and attack their target one on one if they were recruited by that enemy fraction.
Now the player has to think; is that champion I want to recruit a spy or an assassin?