So I've been playing around with trying to build a deck specifically for each Legend. Most of them are obvious or semi-obvious synergies with existing cards.
Archaon - Direct damage deck with strong attack possibilities.
Kairos - Sorceror of Tzeentch synergy, use lots of development stuff.
Malekith - use as many units and supports that remove or trigger off removing opposing units. (Probably the best one)
Morathi - use hexes and asilan to complement her ability. I used the remove power theme of DE.
*Gromm - Seems to fit with Reanimator, but I'd like to see a better deck for him.
Azhag - Fits awesome with self-damage theme. (Possibly second best Destruction Legend)
I don't know all the Order Legends off hand but here's there list.
Tyrion - He seems to be incredible in an indirect/Lizardman build.
*Teclis - Useless? The new Star Dragon previewed seems to be based around a tactic heavy deck. He could fit in that. Would like some ideas for him.
Karl Franz - Obvious synergy with the movement decks like VTHC or Knight based.
*Other Empire - Not sure where he'd fit in. Empire doesn't seem like the strong removal/control type without Verena. Would like some ideas here too.
Vengeance Dwarf - Obviously synergizes well with Reclaim The Fallen type decks. If you can space out your unit removals he can deal massive damage.
Burning Dwarf - Not AS useful, but goes well with several units with similar powers. Good for Slayers deck, imo.
I guess my point here, is that I've found homes for all but 3 of the Legends and I'd like ideas on what to pair them with. And if you have better ideas for homes for the others, I'd love to hear them. I think Legends are the bomb and have changed the way I play the game.