The Free Peoples definitely cycles ferociously and is a bear to overcome. This is slightly different from the deck I played against, isn't it?
Herald to Gil-galad fits nicely for what this deck is doing. The biggest problem I can foresee is if you're playing against an Easterling deck.
Easterling Captain with
Easterling Polearm will devastate you if you can't get Sam out fast enough, but most every deck has a weakness. I might consider dropping Legolas' gear to add the other cards you want, since if Legolas is skirmishing you're in a bad spot already.
I am a big advocate of cycling and pushing the size of the deck out a bit

If you're never decking out then it's not a big deal, but the last thing you want is pressure on your FP to cost your Shadow side the game. Are you able to double consistently?
In King Standard,
Arwen, Fair Elf Maiden is gonna be a big hindrance, though honestly between
Weary and Grima (maybe up to 2 copies?) you should be able to cause some real trouble for any of their fighters. I always throw a copy of
Uruk Spear in to help with Rohan, too. I prefer to have 4x
Vengeance (or a copy of
Kill Them Now to secure the occasional support character kill from a forced assignment) which might help with your fights, and since you're already using
SotE I think you'll find that
Brought Back Alive can be even cheekier. Exhaust a companion with
SotE and then assign him anyway.
What Did You Discover? is one of my favorites for encouraging the opponent to stay put, which is great if you're already going first. One tactic I would consider is not play anything during the shadow phase and dare the Free Peoples to move again. One or two copies of that to pull Ugluk and
Uruk Hunter, plus whatever you've got in hand (hopefully a
Vengeance) and the Free Peoples will regret it. If they don't move, you've got the cycling to get rid of stuff while their Free Peoples events clog up the hand, meaning even fewer minions to stand up to archery. I like Lurtz because he's a great fighter, but I think your twilight might be better spent than on
Orthanc Assassin in most cases.
Overall, tough deck. You had a plan to make a pincushion out of any shadow side, and you succeeded