Keep it simple, keep it safe.

This is a fellowship that I tried to keep simple in how it functions. I also wanted to use Gimli and Legolas.

Opening Hands In Proud Hunters dig out Gather Information. You would like to see Master of the Forge and some card draw. Either a weapon and Foe-hammer or Unlikely Friendship, or We Are Not Idle. Odds are on turn 1 you will need Gimli to defend so you may need to just draw the card and not exhaust him.
In the secrecy deck you want to see some secrecy cards (surprise surprise). Timely Aid and Resourceful being the top priorities. Based on cards in hand you determine who is resourceful.

Turn 1 You should be able to clear the 4 progress needed to gather some intel. The Secrecy deck and Thurindir quests for 10, plus any allies you get out. Find Steward of Gondor and Light of Valinor. Gimli is the Steward, Glorfindel is the light.

Questing The Secrecy deck brings the plain and simple. With low cost/high willpower allies it pumps out a lot of quest power. Thurindir quests for 3 once you clear the side-quest.

Combat Gimli defends almost everything. He should be loaded up with a lot of attachments: Armored Destrier will allow him to defend twice, Lembas can heal and ready, Heir of Mardil goes on him as well, you can wait to trigger Steward until after he defends to ready him for another action. Gondorian Shieldand Dúnedain Warning and Arwen Undómiel can have him at 7 . Legolas and Glorfindel get the weapons and kill kill kill. It is not uncommon to place 3-4 extra progress during combat thanks to Legolas and Blade of Gondolin. Use Quick Strike and Hands Upon the Bow to snipe an enemy and then ready Legolas with Gimli's ability to kill again.

Other thoughts Sneak Attack Gandalf should be a common occurrence, Merry with his Hobbit Pony can let you use his ability to the best potential. Thurindir gets the Steed of the North to help kill and when he attacks alongside Legolas you can decide which hero gets the to be the Proud Hunter.

I have beat Journey Along the Anduin, The Mumakil, Race Across Harad (got the sidequest cleared round 1, and still stayed ahead of the pack), and Foundations of Stone.