S+ Tier Decks
Martell
What can't this deck do? It has the best deterrent in the game in the form of Doran--a veritable scorpion raising it's stinger for your attack. It has admirable defensive measures (Areo, depsite being a fairly meh card for a 3, is great on those battles where you're guessing the play, but still want to be safe), but really shines on offense, as it's the only house with up to 5 swords in the deck. Let's not forget Red Viper either--clearly one of the top 4 cards in the game. Overall a jack of all trades and Master of Offense deck.
S Tier Decks
Tyrell
Another fantastic deck. Mace is a strong card, Loras is terrifying at the right time, and Queen of Thorns can have powerful repercussions at critical moments. You add in a sprinkling of respectable 1 and 2 cards and you have the true jack of all trades deck. However, in my estimation, it just doesn't quite match nor exceed Martell--particularly in one key area: deterrence.
Hypothetical: I have a strong attack coming at you(Tyrell) where we are close to evenly matched involving no footmen. What do you do? If this area is really important will you risk using Loras--and wasting his best ability? Will you risk Mace--even though you aren't using him to his fullest potential? And what if you do use either of them--what did you gain? Well, you kept your area for one turn, but you have caused no casualties, and if another strong attack comes again...then what? Can your counter attack wait another turn?
Therein lies the biggest problem--Tyrell forces opponents to play safe--or at least in a certain manner--but once your opponent adjusts it can be difficult to get the advantage that Mace is designed for--granted, Loras nonetheless is a terrifying prospect--particularly at the right moment.
Stark
A simple, but very effective deck. Eddard is a punishing beast that can decimate on attack or defense. Robb is a respectable 3 card with a useful ability. Roose is the backbone of the deck--making Stark one of the consistently more dangerous foes merely because of the at-will refresh options. Catlynn is treated as waste (perhaps fairly, perhaps not), but with Rodrick and the Blackfish, you have a deck that allows your troops to survive the worst attacks and counter attack with Eddard to punish incursions. Not quite as good as Tyrell--as it lacks the flexibility of Queen of Thorns and the threat and unpredictability of Loras--but still excellent.
Greyjoy
Another straight-forward deck. It does one thing really well--win battles. If I had to sum up what Grejoy's deck's thought process it would have to be: Win this battle now, and hope I'll be stronger next turn. Greyjoy's offensive options are so good, but they really need to be--given where he is on the three tracks, as Greyjoy absolutely must use the early game strength to get into an advantageous position for (hopefully) an early muster, or to get up a few tracks on the impending clash. The deck mostly speaks for itself.
Need to win the seas? Done.
Need to win no matter what on an even fight? Done.
Need to deal some damage--or at least threaten it? Done.
While there are some very ho-hum cards (Asha, Theon) nothing stands out as a liability, and that speaks to the strangth of the deck.
A Tier Decks
Lannister
Lannister actually has a very good deck with two major problems: it's nearest neighbors (GJ & Tyrell) have much more flexible decks, and nearly all of her cards--in order to be most effective--have some inflexibility to them.
Tywin is a great card--two power tokens--particularly in a close game--is nothing to turn your nose up at; it just isn't as sexy as a couple swords.
Gregor is the beacon of hope for the deck and can single handedly decimate armies--but he suffers from the Tyrell issue of opponents adjusting because of him by keeping forces spread out rather than together or turtling to prevent a wipe and attacking in overwhelming force to guarantee the win. When he comes through--if the situation presents itself--it's awe-inspiring.
Hound: A great defensive option, but all your eggs are literally in one basket. Do I use him now--or will it be more crucial later?
Kevan: MUST be attacking...and with Footmen. Potential is very strong, but, again, very situational.
The remaining cards speak for themselves--if the situation calls for them to be effective--they really can be, but if it doesn't...well, hopefully you can out strategize.
B Tier Decks
Baratheon
Just a puzzling deck--a jack of...no trades? It can't seem to decide what it wants to be. Deterrence? Patchface for sure and...Salladhor, I guess? Good defense? Well, no, not really...Salladhor, I guess?. Good Offense? Potentially, but limited as you lose any initiative advantage to gain it. Davos is the only redeeming part of the deck, but even then there just aren't any teeth to it. I suppose something could be said about King's Landing giving Baratheon a power generation advantage--which helps on the tracks--which subsequently helps in battles--but that's a bit too much theory-crafting for ruminations on decks. Overall, this deck just misses the mark. It has some good pieces, but as a whole, it's underwhelming.
So, there you go. Feel free to disagree, discuss... what are other's thoughts?