This is a deck I built up mainly to tackle the HoN + AtS scenarios, but it proved pretty good even against other quests.
It is a Solo deck but it can be adapted for 2-players, paired with a Spirit heavy (best if mono) deck.
It works well against Peril in Pelargir, Into Ithilien and even the Siege of Cair Andros.
Of course, packing no treachery cancellation, it is especially vulnerable to treacheries (The Master's Malice above all).
The only quest it struggles against is The Morgul Vale, since starting at 31 means there is not even a single round to setup before egaging Murzag. While it is usually easy to defeat Stage I and Stage II, without a bit of setup the Nazgul + ridiculous amount of threat in the Staging area will kill you.
The other caveat I have is the Steward's Fear, which I was unable to try due to the fact I do not own it.
This deck also fared well against the RM cycle, demolishing a tough quest such as The Three Trials.
Doomed Numenoreans
Heroes (3)
Boromir (T)
Aragorn (Lo)
Theodred
Allies (19)
2x Gleowine*
3x Master of the Forge
3x Wandering Ent
3x Booming Ent
2x Treebeard*
3x Envoy of Pelargir
3x Gandalf*
Attachments (17)
3x Gondorian Fire
3x Gondorian Shield
3x Steward of Gondor*
3x Celebrian Stone*
2x Sword that was Broken*
3x Blood of Nùmenor
Events (14)
3x Deep Knowledge
3x Daeron's Runes
3x Feint
2x Legacy of Nùmenor
3x The Seeing Stone
Strategy
In the early game you count on Boromir and Doomed cards to have a quick start and keep enemies at bay, knowing that you have Strider's ability at your disposal.
With a bit of luck you are able to muster a small army of allies to help with card draw and combat/questing (ents). In the meanwhile, due to the amazing amout of card draw you should be able to quickly set up Boromir for some heavy Gondorian Fire usage, at which points enemy become much less fearsome.
It is a well-rounded deck able to handle many aspects of the game very well and not reliant on a specific card to appear (the aforementioned Gondorian Fire is not vital due to the Ents and the awesome attacking values of the Heroes).
Theodred is particularly useful in this deck, allowing you to quickly play important cards such as The Sword that was Broken or powering up Boromir for Gondorian Fire in case the Steward of Gondor didn't show up.
While not the most powerful deck around it still is pretty good and I have a lot of fun when playing with it.
Note that I do not have included Sneak Attack since I find SA+Gandalf combo to be boring and unbalancing: when I managed to pull it out it made my victory feel hollow. If you want, however, you can easily add 3x copies of SA in. The additional threat reduction would make this deck much more powerful.
Also posted on BGG.