I just tried to improve my Tactics/Spirit deck and I was really happy with the changes I made, until I lost twice to the first quest. This is supposed to be difficulty 1, but I can't defeat it. Please someone give me a hint regarding the problem with my deck. I know that it could be a matter of luck, I kept getting hit with those web cards where it costs two to untap. But bad luck alone shouldn't be enough to lose twice in a row on a 1 difficulty quest, right?

Anyhow, here's my deck:

ALLIES
3 Gandalf
3 Northern Tracker
3 Wandering Took
2 Beorn
3 Gondorian Spearman
3 Horseback Archer
3 Veteran Axehand

ATTACHMENTS
3 The Favor of the Lady
2 Unexpected Courage
3 Blade of Gondolin
3 Citadel Plate
3 Dwarven Axe
2 Horn of Gondor

EVENTS
3 Galadhrim's Greetings
3 Blade Mastery
3 Feint
3 Quick Strike
1 Swift Strike

If the deck seems fine, maybe I need to look at my strategies.

ALLIES
3 Gandalf
3 Northern Tracker
3 Wandering Took
2 Beorn
3 Gondorian Spearman
-3 Horseback Archer - expensive and for solo the same as Axehand, which costs 1 less
3 Veteran Axehand

ATTACHMENTS
-3 The Favor of the Lady - Lorien Guide is still much less desperate
2 Unexpected Courage
-3 Blade of Gondolin - well, maybe not -3 but I had to fit in 3 Hasty Stroke below
3 Citadel Plate
3 Dwarven Axe
2 Horn of Gondor

EVENTS
3 Galadhrim's Greetings
-3 Blade Mastery - not much need for a non-permanent +1 stat
3 Feint
3 Quick Strike
-1 Swift Strike - IMO, it's better to decide: heavy event wounding tactics or none

Maybe try this:

Eowyn, Dunhere, Gimli.

3 Wandering Took
3 Lorien Guide - sucky, but with willpower
3 Northern Tracker
3 The Galadhrim's Greeting
3 Hasty Stroke - safe undefended damage is very important for Gimli
3 A Test of Will - when revealed is bad
3 Stand and Fight -
2 Dwarven Tomb
2 Unexpected Courage
3 Veteran Axehand
3 Gondorian Spearman
2 Beorn
3 Feint
3 Quick Strike
3 Citadel Plate
3 Dwarven Axe
2 Horn of Gondor
3 Gandalf

Plates to Gimli, Axes to Dunhere. It won't be pure spirit/tactics but you can try Stand and Fight for Faramir or Glewine.

Wanting to stay true to your hero setup, I came up with the following deck. Keep in mind that I play almost exclusively two player games, and some of the cards I'm suggesting I have literally never actually played; for example, I have never played a game with Gimli, despite how awesome he is in theory. Still, I'll provide some thoughts and the rationale behind my suggestions to at least give you another player's perspective:

Heroes
Gimli
Legolas
Eowyn

Allies
3x Gandalf
2x Beorn
3x Gondorian Spearman
3x Veteran Axehand
3x Lorien Guide
3x Wandering Took
3x Westfold Horse-Breaker
2x Northern Tracker

Attachments
3x Blade of Gondolin
3x Horn of Gondor
3x The Favor of the Lady
3x Unexpected Courage
3x Citadel Plate

Events
3x Feint
3x Quick Strike
2x A Test of Will
3x The Galadhrim's Greeting
2x Hasty Stroke

(edit: alternatively, swap out 2 Northern Tracker and 1x Veteran Axehand for 3x Dwarven Axe. Since you're playing with Gimli, you definitely want to take advantage of that card, and read below regarding my thoughts on the Tracker)

Heroes: Although this deck has 2 Tactics heroes, something to keep in mind is that it has roughly equal numbers of Spirit and Tactics cards. As I'm sure you already know, with such powerful Tactics heroes, combat should not be any problem whatsoever for you, but this also leaving us scrambling to be able to be able to quest successfully. Eowyn is an extremely powerful quester, and Gimli isn't too shabby himself; by using cards like Unexpected Courage you can give Gimli extra actions to contribute to questing and attacking, and by using cards like Quick Strike you can dispatch enemies faster to free him and other characters up to contribute to the quest earlier than they would otherwise be able. In a pinch, Westfold Horse-Breaker would also be very useful for readying Gimli.

Allies: I only suggest including 2 copies of Beorn because although he is extremely powerful, a deck with two Tactics heroes should not be having much trouble in the attacking department (especially considering you'll have Gimli and plenty of ways to give him extra attacks), and he's unique and extremely expensive anyhow. Gondorian Spearman is a great defender, and Veteran Axehand is cheap, durable, and an effective attacker.

Now, here's something that is really worth thinking about: Northern Tracker versus Lorien Guide. Since you're talking about playing a single player game, you're only going to be revealing one Encounter card every time you go through staging. Your original build has 3 Northern Trackers, but if you're striving to minimize the amount of threat you have in the staging area (due to having poor Willpower compared to lots of other decks that use fewer Tactics heroes), you do not want to leave locations sitting there contributing their threat any more than absolutely necessary. Northern Tracker is hugely expensive in a deck where you can normally only put one into play every four turns, and even though he has far superior stats to Lorien Guide, they have equivalent willpower, and when it comes down to it, Lorien Guide allows you to put its ability to good use while still keeping the threat in the staging area low. As much as I love Northern Tracker, in your situation I think that Lorien Guide is hands-down the better choice. However, since the pool of cards isn't huge, I included 2 copies of him. However, you could easily swap those out for some Tactics cards of your liking, because I really doubt such a hugely expensive card is going to actually get played very often; and really, for the same amount of resources, 2 Wandering Tooks would contribute double the willpower, and if you aren't using the Tracker's ability anyway... you get what I'm saying. The Horse-Breaker is also a fair quester, its pretty cheap, and although having 1 hit point sucks, it can give a character like Gimil an extra action, which more often than not probably means a one hit KO of almost any creature in the game (up to 14 attack strength? yes please).

Attachments: Blade of Gondolin obviously helps you make desperately needed quest progress, and although Horn of Gondor is unique, you are going to be so desperate for extra Spirit resources that I think its probably advisable to include 3 copies. The Favor of the Lady is generally far safer than having some squishy one willpower ally in play, and Unexpected Courage beyond amazing to help Legolas generate massive quest progress (4 per kill with 2 blades of gondolin adds up very quickly). Like Gimli, Citadel Plate is a card that I have honestly never used, but since you're bold enough to play without any kind of healing seems necessary, and you won't have too much trouble affording it with 2 Tactics heroes.

Events: Feint needs no explanation. Quick Strike lets you avoid having to eat some incoming attacks, and lets you declare more than one attack on the same enemy in one combat round, which is fantastic; I can't imagine much could stand up to two hits from a powered up Gimli. Test of Will and Hasty Stroke have good effects, and they're extremely cheap to play. One Spirit resource, although precious in your deck, can potentially prevent a lot of pain and hardship. Finally, the Galadhrim's Greeting will let you lower threat, which is always a good thing.

Hope that was helpful, and best of luck to you!