These are the cards I'm most excited for.
Naga Sea Witch: 5 for 5/5 - Your cards cost 5.
http://imgur.com/2dRBlFB
I think she might be able to bring some consistency to a Ramp Druid deck that tries to use Aviana. She allows you to make some big power plays with minions that cost 7+ mana and she is a decent sized body herself.
Djinni of Zephyrs: 5 for 4/6 - Buffs on other minions also buff him.
http://imgur.com/mkRolq7
There are a lot of good buffs and there are now neutral minions that have synergy with buffs at 3, 4, and 5 mana slots. This might be the card that opens up those decks.
Raven Idol: 1 mana - Choose to discover a Spell or a Minion
http://imgur.com/KZGoUqf
This is really good. A 1 mana do anything you might need is powerful. There is a chance it doesn't give you a good option, but any card that can help you in both the early game and late game is amazing.
Rumbling Elemental: 4 mana 2/6 - Deal 2 random damage when a battlecry is played.
http://imgur.com/TotXzQz
The deal damage effects are always really powerful. With 6 health this guy might stick to the board. Shaman has some powerful battlecry minions with Fire Elemental, tuskar totemic, Fireguard Destroyer, and Totem Carver. Combo this with the new legendary that doubles battlecry effects and it might be a good deck.
Anyfin Can Happen: 10 mana - Summon 7 murlocs that died
http://imgur.com/m09zdHt
I might play some pally murloc.
Entomb: 6 mana - Choose an enemy minion and Shuffle it into your deck.
http://imgur.com/9n38AK7
This is really good removal. It silences, kills it, and adds a card to your deck. This is absolutely an auto include in Control Priest and will probably replace Mind Control forever.
Unearthed Raper: 3 mana 3/4 - Copy a friendly deathrattle effect
http://imgur.com/JceH0hn
This card will turn death rattle rogue into a thing. It has good stats no matter what and it has good text. This card is going to be broken as hell when it copies a Nerubion Egg and even weaker copies like the Spider will make it incredibly hard to win back the board.