Built this deck originally for duel play, but after some nitpicking I found that its actually quite effective solo in the new Heirs quests; also a lot of fun to play.

Prince Imrahil

Boromir (Leadership)

Beregond

Allies:

Defender of Rammas x3

Guard of the Citadel x3

Errand-Rider x3

Gondorian Spearman x3

Envoy of Pelargir x3

Vassal of the Windlord x3

Faramir x2

Gandalf x3 (core)

Attachments:

Spear of the Citadel x2

Dunedain Warning x3

Dunedain Mark x3

Cram x3

Song of Battle x2

Steward of Gondor x2

Horn of Gondor x1

Events:

Sneak Attack! X2

For Gondor! X2

Behind Strong Walls x3

Feint x2

Valiant Sacrifice x2

-This is an archetype that will obviously get better as we get more gondor cards this cycle, but Boromir is still able to add a nice chuck to your attack which is helpful for both attacking and questing through the "battle" stages, everything else is mostly self explanatory

I really like this deck. I tried Leadership Boromir in a Gondor-themed deck when I first got HoN and got smashed going Into Ithilien. That said, I like the direction that you are going with this deck, it makes me think that I should retool using some of your ideas and try it again.

Some of the new cards inspired me to build a pair of Gondor/Rohan decks representing the Battle of Pelennor Fields. They are definitely more on the thematic side, I fear they would not be able to handle HoN very well, but they were fun to build in any case:

http://hallofbeorn.wordpress.com/2013/01/09/decks-battle-of-the-pelennor-fields/