At first, I thought this card was severely limiting - because the full benefit only applies with Gimli. But a deeper analysis of this card combined with equivalent Hero pairs changed my mind. This is a very underappreciated hero.
Lets compare Legolas plus Gimli, vs. the best quest hero in game - Éowyn plus (another hero). Let's also focus on early game first turn, when every advantage is critical. Both Legolas and Éowyn start with 9 threat, so that is equal.
The first comparison layer is questing Willpower . Spirit Éowyn discards one card to get 5 , and Eowyn is exhausted. Legolas plus Gimli discards one card to get 4 , and only Legolas is exhausted.
And of course, a built in Spirit Hero discard mechanic is useful for the usual Spirit sphere combos: out of sphere Ally play using Stand and Fight, card draw recursion with Elven-light, and you can even negate the discard with Silver Harp.
So with the first comparison layer, Legolas (+Gimli) is almost on par with the best quest Hero in game, Spirit Éowyn (+ some other hero) - each exhausting only themselves while opening up the discard mechanic. Yes, Gimli is also "exposed" to quest action encounter cards, this may be a good or a bad thing - but he certainly gives more hit point options to sop up unexpected quest damage.
We then go to the second comparison layer to see the benefits of the Legolas/Gimli combo. Defending Gimli can ready Legolas in the combat phase for one resource, and also adds 1 attack to Legolas, bringing him to 4 . Thus the combo of these two hero friends brings the following by the end of the first round:
Legolas + Gimli = Three phase actions: 4 to quest, 2 (with 5 hit points backing the defender) vs. an engaged enemy, and 4 to strike back. Cost: 1 card discard, 1 resource spent, 20 starting threat.
What paired hero would it take for Éowyn to match this? We need to get extra actions out of this hero, with decent stats on attacking/defending, at the cost of one resource. Aragorn comes to mind. He comes in at one more threat, but can spend a resource to ready himself after questing. This totals to:
Éowyn+Aragorn = Two phase actions: 7 to quest, and "one of" 2 (with 5 hit points backing the defender) to defend an engaged enemy, OR 3 to strike back. Cost: 1 card discard, 1 resource spent, 21 starting threat.
Basically trading off 3 questing in exchange for an action loss of either defending or attacking (with one less ). Sentinel vs. Ranged can be treated as roughly equivalent multi-player extras.
Is one pair superior to the other? They each have their situational best uses, but I think in the long run, the extra action advantage of the Elf and Dwarf could offset the loss of 3 additional from the "not-fated for each other" human couple, especially in an enemy heavy encounter deck.
Legolas and Gimli can quest, optionally engage, defend, and attack each round. They even start at 20 so you can play with just two heroes and starting secrecy. Meanwhile, Éowyn+Aragorn would not be able to reliably reduce an increasing enemy staging threat, and combat with the pair would be longer, and with more risk, since that duo can only attack, OR defend.
Legolas and Gimli can also add the same Aragorn as the third hero, making for a very thematic and powerful combo. There is no third hero to pair with the Éowyn and Aragorn combo to reach equivalent power.
And with the new contract card, Forth, the Three Hunters! having no allies available makes built-in Hero readying even more important, especially with the thematic trio mentioned here.
Having looked at all this, I think Legolas is a great Hero card. Sure, you have to pair him with Gimli to get the most out of it, but given the analysis above - you should absolutely make that pairing when playing either hero.
This also shows how the card designers made such a thematic pairing in the novels, equally compelling in game. Well done, FFG.