The Hills of Emun Muil (2 player, Round 2, One Core Set)

The Hills are almost impossible to beat in Round 1, due to the need to actually see 20 VP worth of locations, and be able to put 18 progress on them. The most card efficient way to do this is to reveal 2x The Outer Ridge and 2x The East Wall of Rohan, for a total of 20 VP alongside Amon  Hen and Amon Lhaw. We'll be using Legolas again to blow up some Eastern Crows to help clear out locations.

Setup:
Add Amon Hen and Amon Lhaw to the staging area

Deck 1:
Legolas
Dunhere
Eleanor

Hand:
Blade of Gondolin
Northern Tracker
Stand and Fight
Stand and Fight
Strength Of Will
?

Deck 2:
Eowyn
Gloin
Theodred

Hand:
Steward of Gondor
Unexpected Courage
Northern Tracker
Sneak Attack
Snowbourn Scout
Snowbourn Scout


Round 1 Planning:
Draw ? and Sneak Attack
Attach Blade of Gondolin to Legolas
Attach Steward of Gondor to Eowyn, and exhaust it.
Attach Unexpected Courage to Legolas

Round 1 Quest:
Commit Dunhere, Eleanor, Eowyn (Deck 1 discards), Gloin, Theodred (resource to Eowyn) (10 Willpower)
Reveal 2x Eastern Crows, surging into 2x The Outer Ridge (10 total Threat)

Round 1 Travel
Travel to Amon Hen

Round 1 Engagement:
Both Crows engage, one on each deck

Round 1 Combat:
Both attacks go undefended (no shadow effects). Dunhere and Gloin each take 1 damage. Gloin gains a resource.

Legolas kills both crows, clearing Amon Hen, and adding the needed progress to the quest.

Round 1 Refresh:
Raise Threat to X and Y

Round 2 Resource/Planning:
Draw ? and ?
Exhaust Steward of Gondor (5 resources total)
Play Northern Tracker
Deck 1 Play Northern Tracker

Round 2 Quest:
Quest with 2x Northern Tracker (clearing 2x The Outer Ridge, Amon Lhaw at 2/5 progress), Gloin, Theodred (resource to self), Eowyn (Both decks discard), and Dunhere. (12 total Willpower)
Reveal 2x Eastern Crows, surging into 2x The East Wall of Rohan (12 total Threat)

Round 2 Travel:
Travel to Amon Lhaw, exhaust Eleanor to play Strength of Will (4/5 progress).

Round 2 Engagement:
Optionally engage 1 crow, and the second also engages Deck 2.

Round 2 Combat:
Sneak Attack x2 puts Snowbourn Scout x2 into play, clearing one Wall
Each scout blocks a crows, and dies due to a shadow effect boosting attack
Deck 1 plays 2x Stand and Fight to put the scouts back into play (clearing the other Wall)
Legolas attacks and kills a crow, putting the last 2 progress needed on Amon Lhaw

The Dead Marshes (Solo, Round 1)

The Dead Marshes fall, beaten in Round 1 by a single Core set (as released):

Heroes (30 Threat)
Legolas
Glorfindel
Gloin

Hand:
Blade of Gondolin
Protector of Lorien
Sneak Attack
Gandalf
Sneak Attack
?
Draw: ?

Setup: reveal Evil Storm (no effect)

Planning:
Play Blade of Gondolin on Legolas
Play Protector of Lorien on Glorfindel

Quest:
Play Sneak Attack to bring in Gandalf. Draw 3 cards, which are discarded to Protector of Lorien.
Commit Gandalf, Gloin, and Glorfindel to the quest (12 Willpower)

Reveal Eastern Crows, which surges into Despair (no effect).
Discard a 4th card to Protector of Lorien, since this takes place before the errata.
Place 12 progress on stage 1, completing it.

Escape test:
Exhaust no-one, fail the test, add 2 resources to Gollum

Engagement:
Wolf Rider engages

Combat:
Take Eastern Crows attack undefended. Gloin takes 1 damage (and gains 1 resource)
Sneak Attack to bring out Gandalf again, reducing Threat by 5.
Legolas dispatches the crows, adding three progress to Stage 2, and completing the quest.

Exhaust Gandalf for the final Escape test, discarding 2 cards that do not beat Gandalf's Willpower.

Final Score: 25 (Threat) + 1 (damage) + 0 (rounds) - 0 (VP) = 26!

How to beat Journey Down the Anduin in Round 1

The best solution I've come up with to this challenge is three players, and using a third Sneak Attack. For a single core set, it is relatively trivial to beat it solo in 2 rounds, using the same hero lineup and technique as Passage Through Mirkwood.

3 players, 2 core sets, 1 round:

Deck 1:
Legolas
Gimli
Thalin

Hand:
2x Blade of Gondolin
Horn of Gondor
2x Quick Strike
Blade Mastery

Draw: Veteran Axehand

Deck 2:
Aragorn
Theodred
Gloin

Hand:
3x Sneak Attack
2x Son of Anor
Gandalf

Draw: Steward of Gondor

Deck 3:
Eowyn
Dunhere
Eleanor

Hand:
Unexpected Courage
Stand and Fight
(other cards are irrelevant)

Staging: Reveal Hill Troll, Despair x2.

Planning:
Play Steward of Gondor on Eowyn & exhaust it
Play 2x Blade of Gondolin on Legolas
Play Horn of Gondor on Gimli
Play Unexpected Courage on Legolas (3 Spirit resources left on Eowyn)
Use Sneak Attack to put Gandalf into play, dealing 4 damage to the Hill Troll (5/9 HP remaining)
End of phase, return Gandalf to hand, Gimli gains a resource.

Quest:
Discard Son of Anor, Veteran Axehand, and an irrelevant card to boost Eowyn.
Use Stand and Fight to put Son of Anor into play, engaging the Hill Troll.

Commit Gimli, Thalin, Aragorn, Theoden (resource to Gimli), Gloin, Eowyn, and Dunhere to the quest (16 willpower), along with the Son of Anor.

Reveal 2x The Necromancer's Reach (Gimli gains a resource when the Son of Anor dies (total of 3), Gloin gains 2 resources, 14 total damage on heroes)
Reveal Goblin Sniper

Play 2x Sneak Attack to put Gandalf (deal 4 damage to Hill Troll, 1/9 HP remaining) and Son of Anor (engage Goblin Sniper) into play.

Play Blade Mastery to give Legolas +1 Attack
Play Quick Strike and have Legolas ranged attack the Hill Troll, defeating it and adding 4 progress to the quest.
Ready with Unexpected Courage
Play Quick Strike and have Legolas ranged attack the Goblin Sniper, defeating it and completing Stage 1.

Resolve the quest, adding 16 progress and completing stage 2.

Reveal 6 locations for the Forced effect on Stage 3, completing the quest!

How to beat Escape From Dol Guldur on Round 2

In this case, we will need to use 2 decks, but can still use only 1 core set worth of cards (and perfect draws). It might be possible to get a slightly better score by using smaller heroes - but less than 2 rounds is still insane!

Setup: Add 3 objectives to the staging area. Reveal 3 treacheries with no effect.

Deck 1 (29 Threat):
Legolas
Gimli (Held Prisoner)
Gloin

Opening Hand:
Blade of Gondolin
Sneak Attack
Son of Anor
Blade of Gondolin
Feint
For Gondor

Deck 2 (26 Threat):
Eowyn
Eleanor
Beravor

Opening Hand:
Unexpected Courage
Protector of Lorien
Henamarth Riversong
3 other cards

Round 1 Resource/Planning:
Each deck draws a card.
Attach Unexpected Courage to Legolas
Attach Blade of Gondolin to Legolas
Play Henamarth Riversong

Round 1 Quest:
Commit Eowyn (discard 1 card), Eleanor, Beravor, Henamarth, and Gloin (11 total willpower)
Reveal Tower Gate and Iron Shackles (2 total Threat)
Attach Gandalf's Map to Eowyn (26 Threat)
Make 9 progress, completing Stage 1.

Round 1 Travel:
Travel to Tower Gate. Each player puts a 1 ATK Orc Enemy into play

Round 1 Engagement:
No action

Round 1 Combat:
Let both orc attacks go undefended. No Shadow effects.
Gloin takes 1 damage (2 resources)
Elanor takes 1 damage
Legolas attacks each Orc (ranged & unexpected courage), placing 1 progress on Tower Gate, and 5 progress on Stage 2 (5/15)
Free Gimli (1 damage), and add Nazgul (3 def, 9 hp) to the staging area
Pay 1 resource to Sneak Attack Son of Anor into play, engaging the Nazgul
Attack Nazgul with Gimli (3 attack) and Son of Anor (2 attack), dealing 2 damage (7hp remain)
Return Son of Anor to hand

Round 1 Refresh:
Deck 1 to 30 Threat, Deck 2 to 29 Threat. Deck 2 becomes first player.

Round 2 Resource/Planning:
Deck 1 discards Iron Shackles
Deck 2 draws a card (4 arbitrary cards in hand).
Play Blade of Gondolin on Legolas
Play Protector of Lorien on Beravor

Round 2 Quest:
Commit Eowyn (Discard a card), Elanor, Beravor (discard 3 cards), Henamarth (12 total willpower)
Reveal Tower Gate and Iron Shackles (2 total Threat)
Raise Deck 2 Threat by 4 to attach Dungeon Torch and Shadow Key to Beravor (33 Threat)
Make 10 progress, completing stage 2.

Round 2 Travel:
Travel to Tower Gate. Each player puts a 1 ATK Orc Enemy into play

Round 2 Engagement:
No action

Round 2 Combat:
Let both orc attacks go undefended. No Shadow effects.
Gimli takes 1 damage (2 damage)
Elanor takes 1 damage (2 damage)
Play Feint on the Nazgul, no attack.
Legolas attacks an Orc, and readies (ranged & unexpected courage), placing 1 progress on Tower Gate and 3 progress on Stage 3 (3/7)
Play For Gondor!
Attack Nazgul with Gimli (5 attack), Gloin (3 attack) and Legolas (4 attack), dealing 9 damage, defeating the Nazgul, and placing the final 4 progress on Stage 3.

Final Score: 30 (deck 1 Threat) + 33 (deck 2 Threat) + 5 (damage) + 20 (1 round, 2 players) - 0 VP = 83 - or 42 on average! Or 73 with normal counting.

How to beat Passage Through Mirkwood on Round 1.

With a perfect draw, it is possible to beat the first quest on the first round of the game, using only the cards from a single Core Set.

Heroes (27 starting threat):
Legolas
Eowyn
Gloin

Starting Hand:
Sneak Attack
Sneak Attack
Son of Anor
Gandalf
Stand and Fight
Horn of Gondor

Top of Deck:
Valiant Sacrifice
Beoren
Brok Ironfirst

Setup:
Add Forest Spider (2 threat, 1 def, 4 HP) and Old Forest Road (1 threat, 3 QP) to the staging area.

Planning Phase:
Play Horn of Gondor on Eowyn.

Quest Phase:
Pay 1 Leadership resource to Sneak Attack Gandalf into play, killing the Forest Spider.
Quest with Gloin, Gandalf, and Eowyn, discarding Son of Anor to boost Eowyn's Willpower  (11 total willpower)
Reveal Dol Gondor Orcs (dealing 2 damage to Gloin, Gloin gains 2 resources)
Place 8 progress on Stage 1, completing it. (11 willpower - 3 threat)
Return Gandalf to hand. Eowyn gains 1 resource (2 total).
Play Valiant Sacrifice, drawing Beoren and Brok

Travel Phase:
No Action

Engagement:
Engage Dol Gondor Orcs (0 def, 3 HP)

Combat Phase:
Play Sneak Attack to put Beoren into play.
Take attack undefended (no shadow effect), letting Gloin die. Eowyn gains 1 resource (3 total).
Put Brok Ironfist into play.
Exhaust Legolas to attack and defeat the Dol Gondor Orcs.
Place two progress on Stage 2, completing it.
Reveal "Don't leave the path!" - search for Ungoliant's Spawn (2 Def, 9 HP) and put it into play.
Play Stand and Fight to put Son of Anor into play. Engage Ungoliant's Spawn.
Attack Ungoliant's spawn with Beoren (activated for 8 ATK), Son of Anor (2 ATK), and Brok IronFist (2 ATK), dealing 10 damage and winning the game.

Final Score: 27 threat + 9 cost defeated hero + 0 damage + 0 rounds = 36!

Solo Escape from Dol Gondor rules

Setup:
Do not capture one of your heroes. Instead, you are rescuing an objective ally "The Prisoner"
Search the deck for the 3 objective cards, the Nazgul, 1 Tower Gate, and 1 Dungeon Jailer
Attach Gandalf's Map to a Hero of your choice.
Resolve the Travel effect on Tower Gate and make it the active location. Attach Dungeon Torch to it.
Set Shadow Key, Nazgul, and Dungeon Jailer aside, out of play. Add The Prisoner to the staging area.

You cannot place progress on Stage 1 unless Dungeon Torch is attached to a Hero.

When you reveal Stae 2A, add Shadow Key to the staging area, guarded by the Dungeon Jailer previously set aside. Instead of flipping The Prisoner face up, take control of him (and deal him 1 damage).

You cannot place progress on Stage 2 unless Dungeon Key is attached to a Hero.

The Dungeon Jailer game text is active, even when he is set aside.

"The Prisoner" - 0 will, 0 atk, 0 def, 5 hp. The Prisoner is exhausted and cannot ready or be healed. If The Prisoner leaves play, you have lost the game. Forced: if an objective would be shuffled into the Encounter deck, deal 1 damage to The Prisoner instead.

Out of Mirkwood

A custom scenario, to be played in the Hobbit campaign between Flies and Spiders and The Lonely Mountain, or as an independent quest.

Quest 1: The Elf King's Hospitality.
Setup: Remove Orcrist from the Campaign pool. Remove Barrel Room, Keeper of the Keys, and all 6 Elven Guards from the encounter deck, along with the Lake Town Mayor and Lake Town Docks. Add Keeper of the Keys to the staging area, and make Barrel Room the active location.
Quest 1b: (4 quest points)
During each Quest phase, instead of revealing cards from the Encounter deck, each player must chose a set-aside guard and add it to the staging area, or add two resource tokens to this card (if all guards have already been added).

The total Threat in the staging area is increased by 1 for each resource token on this card.

Forced: when the 4th progress token is placed on this card, discard all Elf enemies from play

Barrel Room (Unique Location; 4 Threat, X quest points, 1 VP)
X is equal to the total number of characters in play

Keeper of the Keys (Unique Enemy; 50 engagement level, 4 Threat, 5 ATK, 4 DEF, 7 HP)
Elf.
Forced: after Keeper of the Keys attacks and destroys a character, return him to the staging area.

Elven Guard (Enemy; {22, 25, 28, 31, 34, 37} engagement (one of each), 2 Threat, 4 ATK, 2 DEF, 4 HP)
Elf.
Forced: after Elven Guard attacks and destroys a character, return him to the staging area.

Quest 2: Barrel Rider
When Revealed: Reveal cards from the Encounter deck until the total Threat in the staging area is at least equal to the number of players. Skip the engagement phase this round.
Quest 2b: (SIEGE quest; 14 quest points)
Forced: After placing any amount of progress on this quest, the players as a group must assign that much damage among characters they control (to a maximum of the number of characters committed to the quest).

Quest 3: Masters of the Lake
When Revealed: add the Lake Town Mayor to the staging area, make Lake Town Docks the active location (discarding any previous location)
Quest 3b: (8 quest points)
The players cannot complete this phase unless the Lake Town Mayor is in the victory display.

Laketown Docks (x1) - Unique, 3 Threat, 5 Quest Points, 3 VP
While Laketown Docks is the active location, each Hero gains "Action: Exhaust this character to heal 1 damage from it"

Lake Town Mayor (Unique Enemy; 1 engagement level, X Threat, 2 ATK, 6 DEF, 1 HP, 4 VP)
X is the total number of players. The Mayor cannot leave the staging area, and is immune to player card effects. Attacks against the Mayor use Willpower instead of Attack.

Each hero gains "Pay 1 resource from this hero's pool, this hero can attack the Lake Town Mayor this phase as if he was engaged with you."

Remaining Quest Deck (30 cards) - 2 location, 1 enemy, 2 treachery removed for Easy Mode

Locations (10):
Banks of the River (x4) - 1 Threat, 3 Quest Points
Surge
{if this attack is undefended, raise the defending player's Threat by 3}

Rapids (x2) - 3 Threat, 2 Quest Points {one with difficulty indicator}
Forced: after any amount of progress is placed on the Rapids, each player must deal 2 damage to an ally he controls.

Streets of Laketown (x2) - 2 Threat, 2 Quest Points
Immune to Player card effects
{attacking enemy gets +2 Defense for remainder of the round}

Staging Area (x1) - 4 Threat, X Quest Points {difficulty indicator}
X is the total number of characters in play
{Raise defending player's Threat by 1 for each damaged character he controls}

Manor House (x1) - Unique, 1 Threat, 4 Quest Points
Travel: Raise each player's Threat by 3. Each player may heal up to 3 damage from his or her characters.
{Heal all damage on attacking enemy}

Enemies (12):
Goblin Archer (x3) - 33 engagement; 1 Threat, 3 ATK, 1 DEF, 3 HP. Goblin. Orc.
Archery 1
{deal 1 damage to defending character}

Goblin Scout (x2) - 45 engagement; 3 Threat, 4 ATK, 3 DEF, 3 HP. Goblin Orc.
Forced: at the end of the round, raise each player's Threat by 1.

Wargs (x2) - 20 engagement; 2 Threat, 3 ATK, 1 DEF, 3 HP. Creature.
Forced: if Wargs is dealt a shadow card with no effect, return Wargs to the staging area after it attacks.
{+1 attack; +2 if undefended}

Black Forest Bats (x2) - 15 engagement; 1 Threat, 1 ATK, 0 DEF, 2 HP. Creature
When Revealed: Each player must chose 1 character committed to the quest and remove them from the quest.

Man of Dale (x2) - 28 engagement; 2 Threat, 3 ATK, 2 DEF, 4 HP.
When Revealed: Any player may exhaust a Hero he or she controls with Willpower of 3 or higher to discard Man of Dale
{cancel this attack}

Goblin Chieftain (x1) - {difficulty} 35 engagement, 2 Threat, 3 ATK, 3 DEF, 6 HP, 4 VP. Goblin, Orc.
While Chieftain is in the staging area, other Goblins have +1 Threat and +1 Attack.
When Chieftain attacks, deal it an additional Shadow card.
{If attacking enemy is a Goblin or Creature, deal it 2 additional Shadow cards}

Treachery (8):
Chilled to the Bone (x2): When Revealed: attach to a Hero. Counts as a Condition attachment with "Attached Hero gets -1 Willpower, -1 Attack, and -1 Def for each damage on him."

Fighting among Friends (x2) When Revealed: The first player names a sphere. Then, all non-baggins characters not of that sphere are removed from the quest
{+1 attack; +2 if undefended}

Hatred Rekindled (x3) {2 with difficulty} When Revealed: Each engaged enemy makes an attack (without shadow cards). If no attacks occur, Surge.
{Attacking enemy makes an additional attack}

Elven Delegation (x1) Surge. When Revealed: shuffle each Elf enemy from the encounter discard pile into the deck.
{Shuffle this card back into the Encounter deck}