I would definitely have to go with Bushido! Samurai could've been one of the coolest tribes, but Wizard's made them really boring, and the tribe doesn't have a ton of creatures in it. Maybe having like an additional benefit for each creature you have that has Bushido, or just by making all of your creatures Samurai with Bushido X where X is it's power. I think they could do a lot with this, especially with more combat manipulation focused card like
Fumiko the Lowblood! I think Naya colors would be great for this, as most Samurai are either red or white, and green gives access to ramp and
Isao, Enlightened Bushi, the only green Samurai...
Another cool one that Wizards could mess with would maybe
the Champion mechanic from Lorwyn block? It seemed lackluster, but I think if the Champions had better payoffs it would be quite a fun mechanic with blink.
And Finally, also from Lorwyn (I think), the Clash mechanic needs to happen more, and the stakes need to be raised higher! I can imagine having a ton of fun with a "clash tribal" EDH deck, but there is not enough cards that are worth running to make it a viable option.