I decided to engage in an Against the Shadow campaign (all 9 scenarios from the Deluxe and subsequent cycle) and do it with a full Gondor Fellowship. There are now many Gondor heroes and it's possible to have that line-up, as I consider Pippin to be kind of Gondorian, the only "stranger" here is Beravor, who is still a kinswoman to her fellow Rangers of Ithilien.

Be aware that my comments and piloting tips below are taken from my experience at replaying this cycle, which has lots of Battle and Siege questing. I don't know how it would consistently fare against a more standard cycle. I advise you try Against the Shadow with those decks, it's so epic!

In today's meta, Gondor is by no means the strongest trait, especially in a solo environment. Gondor does not have strong quester from the get-go, and is very dependant on getting allies out, bolstered by Visionary Leadership to muster enough . But, in a multiplayer environment, the trait is absolutely amazing. I've used cards in those decks I've never used before and to great effect.

Yes, Gondor is all about global boosting / readying effects and how to manage them. Especially, the cards For Gondor!, Strength of Arms or Light the Beacons. The first two events are already quite good with 2 players, but they are just insane with 4 players. Coupled with Boromir's ability and Visionary Leadership, your host of Gondorian allies should be Standard/Battle/Siege questing with absolutely no issue. Just ensure you mulligan for the right allies at the beginning of the quest depending on whether or not the first quest stage bears a keyword.

While Light the Beacons is seldom used, due to its hefty cost, it is a card that can win your game. In this fellowship, the deck has a support role, and is often left with enough resources to play the card, especially since Denethor can fuel resources towards it. I mean just read the card! Just Siege quest with every character and have Beregond defend everything for at least 6 (if not 8 if equipped with Gondorian Shield).

Playing monospheres also allows the use of monosphere cards: Advance Warning, Strength of Arms, Shadows Give Way, Thicket of Spears, Trained for War, Against the Shadow, Knight of Minas Tirith and White Tower Watchman, as well as all Record attachments. All those cards are clearly Gondor theme and really pull their weight to smooth those Battle/Siege keywords depending on what you have on table.

The Leadership Deck

This is the centerpiece of the Fellowship, because it plays nearly all the global effects. It's pretty straightforward, and Denethor makes it so easier to get the engine running from turn one. Hard mulligan for Steward of Gondor, Visionary Leadership if it's a normal quest, and then some allies. Having a For Gondor! in there is also always nice. Never, never, never hesitate to play Campfire Tales. 1 resource 4 cards is simply unbeatable.

The Lore Deck

Is a Trap deck, simple as that. Play your traps and benefit from it. You're also the healer of the group thanks to Warden of Healing and Ioreth, and you're in charge of card draw by holding back Beravor or having her being Wingfoot (since you're nearly always revealing an enemy, just name enemy). Don't forget Forest Snare can attach to enemies engaged with other players! The Advance Warning + Arrows from the Trees is real, don't underestimate it and have deck save 3 resources to get the full effect of it. If you can play it, just do it. 3 damage to every enemy is insane.

The Tactics Deck

Is obviously the combat deck, helped by the Rangers of Ithilien and deck. Armor attachment goes on Beregond, top priority, then just spread the love on Denethor, Eleanor, Mablung, etc. Prince Imrahil is good target for Heir of Mardil since he's good at questing with all of his stats and should be able to ready thanks to Denethor, then trigger his action, get a Knight of Minas Tirith and trigger Mablung resource generation.

The Spirit Deck

Is clunky but actually works pretty well. It's a control and questing deck. You can defend a bit and sometimes attack, but your primary role is to manage Treacheries with Eleanor and A Test of Will, Shadow Effects with Shadows Give Way and Hasty Stroke and threat with the The Galadhrim's Greeting. It's by no means not a Caldara deck, but it still includes some discard effects with Emery and the Steed of Imladris, so that you can ditch Caldara in favor of two strong questing allies in the late game.

A few side notes

• who said Minas Tirith Lampwright was a dud card? It's actually pretty great, I like to use it against Treacheries or Mumakil, especially since it can work so well with Interrogation.
• the "pay from only one hero's resource pool allies", namely Knight of the White Tower, Linhir Sea-captain and Master Ironsmith are way better in practice than in theory, since you can manage cleverly your resources and spread the ones with all those Errand-rider
• surprisingly, Blood of Númenor and Gondorian Fire are not the star cards! Since we usually get enough stat powering thanks to global effects in the early and mid game, I usually put both of them on Denethor (who is the Steward of Gondor right?), which becomes a beast and can handle boss enemies, like a boss! Just save a Behind Strong Walls or Desperate Defense to ready him.
• Herald of Anórien is not really good 4-players, he's too much threat increase for his cost and effect, so I usually ignore his Response. I included it because he gives flexibility to questing with a 2/1/1 stat line. But I'd certainly recommend a good old Guard of the Citadel or Pelargir Ship Captain over him in quest where you fell he's not needed.
• Man the Walls is a good card. Just play allies that don't quest like the Warden of Healing, or play an ally you know you'll hold back for combat (which is virtually every ally thanks to Boromir's boost and For Gondor!).
• Livery of the Tower on Eleanor or Denethor early game can really help defend in a pinch, but of course shouldn't be abused, as it's quite expensive.
• Just Valour Doom Hangs Still and get your threat back with The Galadhrim's Greeting, combat hard kill every enemy in play, then breeze through the remaining turns.

Side-board

Is global and includes:

• Of course Condition removal tech: Power of Orthanc, Bulwark of the West
• Location control: Distant Stars, Expert Trackers, Backtrack
• More threat reduction: Secret Vigil should be in the side-board

Other cards worth considering

• Make it more swarmy with Legacy of Númenor, Deep Knowledge, The Seeing-stone to grab the two previous cards, and A Very Good Tale to benefit from those Citadel Custodian played at no cost
• The spoiled Derufin ally, 1/2/1 statline, which can be boosted the same way as other Gondorians, and has the Ranged keyword, with some Threat reduction. He's retievable by Caldara's effect.