Naya has been one of the better midrange decks since it earned the name Naya. It’s fallen off a bit, but some powerful new legends may shake that up.
Thalia’s Lancers is the centerpiece to any legend deck. A 4/4 first strike for 5 is fine in that it can get around Spell Queller and defend the ground against most threats, but the card advantage is what turns it into a Constructed playable. By having a nice enters-the-battlefield ability, you’re adding resilience against Reflector Mage and adding the utility of being able to get something powerful from your library. This brings a number of singleton legends to work with.
Bruna, the Fading Light and Gisela, the Broken Blade are the most obvious Eldritch Moon inclusions. We’ve seen what they can do in WB Control, but their just as effective here. Bruna is an excellent card in any deck with Thalia’s Lancers, as she can return them after they fetch her up. Gisela is a solid card that is taken down a peg due to its weakness against both Queller and Reflector Mage. Combined, however, they win the game almost automatically.
With that Eldritch Moon backbone, all of the other awesome Naya legends can be added to the folded. Archangel Avacyn has been format defining over the past several months. The Dragonlords in both Atarka and Dromoka can both dominate different kinds of games while also allowing you to come back from far behind. Sigarda, Heron’s Grace provides another angle by flooding the board.
While this is effectively a GW deck splashing a bit of red for cards like Dragonlord Atarka, Oath of Nissa does allow you to play cards like Chandra, Flamecaller and Nahiri, the Harbinger, and not have to worry as much about how to cast them. Chandra is an excellent sweeper that turns into a game-winner. Nahiri is already solid, but even moreso with all of these awesome legends to go get when you reach the ultimate.