Smeagol, Frodo, and Sam run into some Easterlings at The Black Gate.
Free Peoples: (Starting Sam and Smeagol. I recommend a medium bid, 1-3)
This setup always tends to do well in my experience, albeit at the expense of moving slowly. Combos are fun though. 2 extra starting Fellowship twilight to use bolstering the deck, I think Ranger of Ithilien would probably do best -- 8 strength when it's needed at the start, to be killed off when it's not to choke a bit better. Less thematic though so I'm trying this first. Dagger Strike is in for the damage bonus, especially to kill a fierce minion. The extra strength doesn't hurt, of course, but remember that this game is a race. Many decks can survive anything when moving one site per turn, and usually that's not enough!
This deck is the most "glass cannon" of the bunch. Smeagol can reach absurd strengths or wound minions to win skirmishes, peeling off burdens with Not Listening and getting rid of troublesome minions with Don't Follow the Lights. You've got to get it all though.
Two shadows require specific counter cards. The Nazgul in the Shire deck will suffer greatly against Don't Follow the Lights, but Black Breath on either of your Hobbits (likely followed by a Blade Tip) is bad news. Seven We Had is there for it, and may even need to be upped for the Edge of Fangorn and Edoras shadows which will also be playing Shadow conditions on your companions (mostly Sam).
The other is the Helm's Deep Parapets archery bomb -- if they can load all 5 machines up, you will go from a fully-healed fellowship to an exhausted fellowship and that's before the archery fire from minions. Nice Imitation is there for this, basically adding 2 vitality before someone dies. It'll come in handy everywhere, of course. You can't use The Ring to soak archery fire so use it when losing skirmishes when necessary to fuel Shire Countryside. I'm considering using Isildur's Bane which may add some wounds to the fellowship's tolerance and hopefully free up these 2 card slots for more exciting stuff. Depends on how the skirmishes and bomb go.
One last interaction, note that Bounder doesn't stack with Sam. He's there purely for Frodo. If you make it to site 9 with Bounder, swords, Sam, and 2 copies of A Promise, your opponent will need to put over 20 strength on both Frodo and Sam to kill them. Throw in Smeagol and whatever events you have in hand and most Shadows will have missed their chance. The trick is getting there before an opponent does ;) That's mostly determined by your Shadow's ability to slow the opponent down, so...
Shadow:
The only corruption Shadow, which I tried to dampen slightly by relying more on Gollum than I normally would, the aim there is to give Ents and Rohan in particular a fair shot. The site path alone can add 5+ burdens though, so it won't take much to put FPs in danger. Easterling Captain is the powerhouse, turning those burdens into stopping power. Easterling Army is, of course, no slouch himself, and unneeded copies of Small Hope threaten overwhelms too.
Small Hope puts Gollum at 7 strength and 4 vitality, which is tough for most decks to kill and generally means surviving to the regroup phase for Heavy burden. It's only a matter of time for most decks until they are corrupted.
The Ithilien match is worth discussing because Faramir's Rangers are all Ring-bound: you won't be able to use your Lieutenant and Guard to add burdens and Frodo will remove burdens. There is a card (Gathering to the Summons) which was made for this matchup, but I need to see how the two fare in-game before I consider it. Easterling Polearm ought to put enough of a damper in things that victory is possible even if corruption isn't.
Oh, and one last note: all versions of Sam are considered "Ring-bound" even if it isn't printed on the card. You won't be adding burdens against Sam, Son of Hamfast, I'm afraid.