I'm tinkering around with my Leadership/Spirit deck. It is for questing and threat control and works in combination with a lore/tactics deck which has fighting, healing and card drawing duties.
So far I used Theodred (Questing/Resource gathering) + Eleanor (canceling treacheries/blocking small enemies) + Eowyn (questing) but I'm not sure about Eleanor because her ability is not as good as "A Test of Will". Sometimes we even decide not to cancel a treachery because we dont want to draw another encounter card.
Now, with Frodo on the horizon, would you replace Eleanor with him in this deck? They both have the same starting threat, just Frodo has one more willpower and one less hitpoint. Obviously he would do questing and might be used for blocking when needed. My Spirit/Leadership deck normally does not get involved into fights much and has only "utility" allies (Northern Tracker, Lorien Guide, Faramir for questing), Took for threat control and Snowborn Scout/Silverlode Archer (Meat shield and helping the other deck).