I love the fellowship contract. Anytime I feel like I am adding too many unique allies, I just take out the non-uniques and throw in the contract. Solves all problems.
Well, in this case, you might be flipping that contract over a lot. Rohan allies tend to leave play a lot. The key component of making this deck work with the contract is to keep Gamling ready as often as you can. There aren't too many good ways to do this without leadership, but Spare Hood and Cloak is one of the better ways, as I anticipate some characters are going to be ready towards the end of the round. To Arms!is another way to get there, if you have either the cloak or the Bow of Yew on him.
As much as you can, play your tactics allies after the quest phase. Guthlaf, for example, is free thanks to his ability, Theoden's and Hirgon's together. Don't be afraid to doom it up, you've got threat reduction in deck. Ioreth would be another good early round pull because you won't be using lore resources otherwise (unless you put Song of Travel on Grima).
I'd mulligan for Song of Travel, as most of the expensive things come from spirit. Sword-thainis a card for Gamling as a way to produce more spirit resources and so that he can be a target for some readying hero effects, such as Unexpected Courage.
I imagine that this deck doesn't quest for a whole lot out the gate, so keep that in mind.