For the Priest deck, I'd suggest Hogger, Sylvanas, Harrison Jones, or Millhouse Manastorm.
Hogger provides you a minimum of one taunt card, he can easily win you a game if he's left unchecked, and he's a great counter to Deathwing (or pretty much any situation where your opponent has only one creature on the board). Unless you are going to die the turn you play him, Hogger > other 6 mana taunt options. Plus, he's super powerful and it takes forty people to kill him, while Hearthstone only allows seven creatures plus one hero per player. OP!
Sylvanas is a potential three-for-one and another possible counter for Ysera, something Priests are sorely lacking in. She's also a midgame body, albeit an overpriced one, but her deathrattle more than makes up for the stats. Unfortunately, Druids, Mages, and Shamans basically get a free pass to ignore her death rattle, thanks to Keeper of the Grove, Polymorph, and Hex, respectively. She's still a 1 for 1 in those situations, though.
Harrison Jones is another overpriced midgame body; he's a Chillwind Yeti that costs one extra mana and has inferior stat distribution, in exchange for a situational battlecry. However, that battlecry is very useful in certain situations that are otherwise problematic for priests: it can help you draw enough damage to kill Jaraxxus, you can deliberately trigger a hunter's traps and then Jones his Eaglehorn Bow, or you can turn a paladin's SoJ-enhanced horde into a Lay on Hands for you. It could also have wonderful effects on a Doomhammer, but I usually find myself using it earlier in that matchup to remove a Stormforged Axe. Yeah, you COULD just run an Ooze instead, but 2-drop slots are much more competitive in Priest decks than 5-.
Millhouse can be useful in Priest decks, as you can keep him up and get insane value out of him with your hero power and/or PW:S. His battlecry isn't THAT bad, either, unless your opponent is a Mage who happens to have two Fireballs and two Pyroblasts in hand. If you play him on turn 2, the worst a non-mage opponent could do in most cases is a one-for-one trade for Millhouse; if they waste direct damage spells hitting you in the face, that's usually to your advantage. Don't play him against a Mage, Shaman, or Hunter, though - Mage has the potential to outright kill you and Hunter/Shaman have spells that give them creatures.