Well, so these I claim to be highly thematic, basically the only three cards that do not fall into the lore of Rohan or Gondor specifically, are Gandalf, A Very Good Tale and Sneak Attack. Gandalf however seems fit to any region and A Very Good Tale is sort of his own.
The disadvantage of these decks is that they do not pair so well with other decks or stand on their own without tweaking. However, the possible tweaking is very minor in case of the Gondor deck which basically just removes Mutual Accord and replaces it with say For Gondor! or a third copy of one of the cards that features twice. Rohan deck is also not terrible solo but quite a few cards and especially attachments are meant to be targeting the Gondor deck.
I do not think I have posted a deck on the site in over two years, and I am only doing so because I have tried these over many dozen games and they seem to be working excellently.
So I hope these will help to beginners and be an option for theme builders.
Gondor
Heroes: Boromir, Prince Imrahil, Théodred
Deck:
Snowbourn Scout x3
Squire of the Citadel x3
Errand-rider x3
Pelargir Ship Captain x3
Envoy of Pelargir x3
White Tower Watchman x3
Faramir x1
Denethor x1
Citadel Custodian x2
Gandalf x3
Visionary Leadership x3
Steward of Gondor x3
Tome of Atanatar x3
Wealth of Gondor x2
Mutual Accord x3
A Very Good Tale x3
Sneak Attack x3
Valiant Sacrifice x3
Strength of Arms x2
Rohan
Heroes: Éomer, Éowyn, Eleanor
Deck:
Minas Tirith Lampwright x3
Westfold Horse-breeder x3
Westfold Horse-breaker x3
The Riddermark's Finest x3
Escort from Edoras x3
Westfold Outrider x3
Blood of Númenor x1
Gondorian Fire x3
Gondorian Shield x3
Horn of Gondor x3
Captain of Gondor x1
Rohan Warhorse x2
Steed of the Mark x2
Gondorian Discipline x3
Behind Strong Walls x3
Mustering the Rohirrim x3
Forth Éorlingas! x2
Astonishing Speed x3
Stand and Fight x3
Notes:
Boromir is obviously Leadership.
Gandalf is core.
Captain of Gondor is a future release, add another Mount or second Blood of Númenor if not into proxy.
No Feint, having tested this a lot against the Battle of Lake-town (which they were in the end beating repeatedly) where Feint is useless, and with the army of allies, or some potentially great defenders, they can do without (though in general, of course, Feint is superb).
No A Test of Will. Just to prove Eleanor, I guess.
Steward of Gondor goes on Théodred who can become much more than your usual money-maker: he can get Steed of the Mark, Gondorian Fire (after Steward of Mutual Accord) and be a decent quester and excellent attacker in the same round, all the better when Forth Éorlingas is played.
Quite a few things target Boromir: Horn of Gondor (not just for theme), Gondorian Fire, Blood of Númenor (well, just a copy, it is not that needed but never a waste, especially when shadows steal attachments), Gondorian Shield, Captain of Gondor, Steed of the Mark, even Rohan Warhorse after Accord.
Share wealth, obviously.
It is useful to have a Tome of Atanatar before playing A Very Good Tale, so that you can immediately use one of the discarded events.
Do not hesitate to use Mutual Accord even during planning to get ahead, even getting a cheap Citadel Custodian and applying Warhorse to Boromir or Fire to Théodred can help a lot (Tome shall help recycling Accord when needed).
Do not hesitate to cancel early damage from Boromir or Imrahil if you know Denethor shall enter play.
Enjoy!