I thought it might be fun to take a look at the new starter decks and see how I might try to upgrade them, using only cards from the Revised Core set and the four starter decks themselves. Some of these decks could be played together still, while others (primarily Dwarf - Gondor and Gondor - Rohan) do use some of the cards from other starter decks, so you wouldn't be able to build all four of my "upgraded decks" at once. This would primarily be a way for a solo player, or 2p group, to start slowly deckbuilding by making some small changes to the existing decks while trying to keep the overall idea of the deck the same.
The Gondor deck, much like the Silvan starter, seemed pretty solid to me right out of the box, with a few exceptions. Pillars of the Kings was the big issue, in that there was no real combination of heroes you could utilize that started at 30 or less threat to actually be able to get the card draw out of it. With that In mind, I decided to basically take all of the Valour (40 threat or higher) support out of the deck and instead load it up to be a pure swarm deck with the addition of a few more allies and A Very Good Tale from the Dwarves of Durin starter set.
Early game willpower will definitely be the issue here, and I can certainly see Mablung remaining a better hero choice than Beregond for many quests just based on that alone, especially with Gondorian Shield on him or some Defender of Rammas helping out. I would swap in Beregond for multiplayer for the Sentinel if the other deck(s) can cover that turn 1 or turn 2 willpower deficit, since this deck should be able to pump a lot of questing out once it can get Visionary Leadership on the table.