Halbarad is a hero I've been using a lot lately in Dunedain decks and he's done good work so I wanted to take some time to sing his praises. He doesn't seem to get that much love in general...
Firstly, Dunedain are cool, the Grey Company are cool, and Halbarad is one of the few named such characters to appear in the books. In the books, he's tight with Aragorn and I'd argue they work well together in the game too. High marks on that front.
In game terms, he's got two useful traits and well-rounded stats so can be tooled up for anything. Good then, that he has inbuilt action advantage ("does not exhaust...")! Of course the player pays for this by being engaged with an enemy, which can be a high cost, depending on the situation. Because of this, Halbarad is generally going to be better off in a more combat focused deck - there could be corner cases where you're playing opposite someone with spare sentinel and/or where Forest Snare is an option, but really he is designed with facilitating combat in mind.
How hard is his first ability to get set up? Well, with Halbarad's second ability (you can optionally engage up to two enemies per turn!), you shouldn't be short on engaged enemies, except possibly in solo play when you're at the mercy of encounter deck reveals. Turn one, he'll often need to exhaust to quest, but some quests start you engaged and there are other tools to go and grab an enemy before questing.
The extra optional engagement may not seem like a lot but I've found it incredibly useful in a lot of situations, typically in two player games (but it could shine even more often in higher player counts). You can save a partner having to engage a nasty enemy, you can pull more than one high engagement cost enemy out of the staging area and get around some of those evil encounter deck tricks (remember Goblin Sniper? How about Lossarnach Bandit and Zealous Traitor from Heirs of Numenor? Halbarad laughs at them). Honestly, there are many times that his second ability has been clutch, particularly in sparing a partner deck a very nasty combat phase.
Who/what does he play well with? Dúnedain Hunter to trigger his ability turn one; Star Brooch and Celebrían's Stone for a quest boost; Roheryn; or boosts depending on need - I usually go with eg Dúnedain Warning in sphere. Since the strategy is engaging enemies - and keeping at least one around - the deck needs defence. I've found Dúnedain Watcher and Guardian of Arnor make a great team and are in sphere. Halbarad pairs best with for all that combat nonsense. I've been using him with Aragorn and making good use of Sword that was Broken.
Who is he competing against? Amarthiúl and Aragorn if you just want a single hero - if you're including Dunedain cards, you'll probably want at least one! His ally version (Halbarad) - I can see how the ally could be good, but haven't used him yet. There are cheaper heroes will better willpower (Sam Gamgee) or resource acceleration (Théodred, Denethor) which mean Halbarad doesn't get much of a look in for people looking to splash . He really suits a certain style of play so perhaps that why I don't see him used in many non-Dunedain decks.
He may not be flashy, but he's a solid glue hero in Dunedain decks and with a few attachments can become a machine in 3 phases of the turn (questing, engagement and combat).
Some nice uses of Halbarad (with credit to the creators Gizlivadi, Seastan and Stokesbook):