A few more ideas!
Hmm... for Hafgan, what about instead of granting all units Shock/Combat I, you could make goblins a bit more than a nuisance by allowing them (but not other recon units) to use
metal weapons. And then, grant +1 poison strength at the Poisons tech. It'd mean that you'd have pretty much a neverending supply of not-altogether-worthless goblins to hurl at the enemy! Not near so strong as regular orcs, but you can pump them out at a ridiculous rate. Perhaps call it "Horde." Alternatively (or in addition, since Goblins still won't be very strong), give them Financial for hammers, allowing an even greater quantity of units to be brought to bear.
For Kane, I'd think about Decadent-- which would grant +50% (!) gold, but would also grant the Ostentatious promotion to all units, which causes them to give +10 hammers to any unit that kills them (commerce would be better, but I'm not sure it could be done with the current XML setup.) So you'd be more powerful economically, but also a
much more tempting target for invaders. (Could be "understood" by the AI just as a diplomatic penalty.)
For Emma, how about Shamanistic? Grants Spirit Guide to all animal units, and maybe turns them into Beasts.
For Mahon the Butcher, give him Bloodthirsty-- grants a building that gives -80% unhappiness from rushing buildings, plus a promotion to all units granting +5 food from each combat. You'd really have no end to potential uses for the surplus population...
Veinhunter could have a promotion, granted to all units, that gives the ability to Move Impassible. Plus, an Autoacquire/Mustmaintain that grants stealth in mountains. (Call it "underminer."
)
I was also thinking that Furia the Mad could have Adaptive/Aggressive, but also be Psychotic, which causes non-Hero, non-Arcane units in enemy territory to randomly go Enraged in enemy territory.
Perhaps a trait for Riuros of the Illians, to be combined with Barbarian: Allow him to build Frostling units, but these units would come with a promotion with a 100% betrayal chance (so they'd immediately go barbarian.) An easy way to harass the neighbors! You could sweeten the deal by making the frostlings half-off (or 2/3 off) what a normal unit of that strength would cost.
Omniscient: Allows you to build a building that grants units in the city +9 to sight range; grants all units Sentry.
Anyway, just a few more thoughts.
EDIT
Malchavic:
Conjuror: Grants "strength of the void" to all units that come out of Planar Gates; say, +2 unholy strength? Additionally, double planar gate build speed. Makes the PG a really big part of the strategy!
Gosea:
Prophetic: First, +100% to the building of Savants, and Second, allows a semi-clone of the Stigmata on the Unborn (in that it ONLY grants the beakers-per-city, not the mana or AC.) Best spread that AV far and wide!