My wife and I have been playing this game since the first cycle, and recently we sat down to do an exhaustive study of the best pair of decks for synergy and efficiency at moving through quests. After trying a lot of different ideas and hero combinations, we settled on the following.
Ironically, I started with what I consider the "best" solo deck and modified it to fit what was needed for a two-player variant.
Heroes - Eowyn, Glorfindel, Beravor
Starting Threat - 24
Allies (18)
Arwen Undomiel x3
Warden of Healing x2
Bofur x3
Mirkwood Runner x3
Rivendell Minstrel x1
Northern Tracker x3
Gandalf (Core Set) x3
Events (21)
Stand and Fight x3
Elrond's Counsel x3
Daeron's Runes x3
Hasty Stroke x3
A Test of Will x3
Dwarven Tomb x3
The Galadhrim's Greeting x3
Attachments (11)
Song of Wisdom x1
Light of Valinor x2
Protector of Lorien x2
Asfaloth x2
A Burning Brand x2
Unexpected Courage x2
So the goal of this deck, obviously, is to handle questing while managing smaller threats on its own. Beravor can exhaust for card drawing on either side of the table once each turn, and with UC I can also quest or block as needed.
The partner deck does the opposite.
Heroes - Denethor, Mirlonde, Legolas
Starting threat - 23
Allies (23)
Warden of Healing x1
Vassal of the Windlord x3
Gondorian Spearman x2
Gleowine x2
Defender of Ramas x3
Dori x1
Daughter of the Nimrodel x2
Ithilien Archer x3
Rivendell Minstrel x1
Haldir of Lorien x1
Gildor Inglorion x1
Gandalf (Core Set) x3
Events (16)
Mithrandir's Advice x3
Infighting x2
Hail of Stones x2
Feint x3
Behind Strong Walls x3
Quick Strike x3
Attachments (11)
Song of Battle x2
Protector of Lorien x2
Rivendell Bow x2
Rivendell Blade x2
Gondorian Shield x3
Legolas is probably my favorite hero in the game. There were a few times when we just couldn't break 0 on questing but he still got us through the stage or a difficult location we just couldn't handle if the turn had ended with that thing on the board. I thought about cutting down to 2 Unexpected Courages, but I frequently drop the attachments in the order of Denethor, Legolas, Beravor.
The Rivendell Bows are another card that seem a little redundant at first, but there are a lot of options for it. The most obvious use is Legolas for that +1 attack, but Mirlonde, Glorfindel, the Mirkwood Runners, and Gildor can all benefit from them as well.
I plan to include some of the Isengard cards into these decks - like the 0 cost Lore card that lets everyone draw 2 for 2 threat to replace Mithrandir's Advice - but for the moment, I don't think there is a better pair of a decks out there. These could stand some minor tweaking, but it really comes down to personal play preference at that point, and how much you're willing to spend on extra encounter packs just for a couple of player cards (like having 3 more Wardens of Healing instead of falling back on the subpar Daughter).
I'm always willing to entertain constructive criticism so please feel free to share your thoughts.