I had a Rohan plains deck that i used to play a long time ago, so i may have some suggestions on the freeps side.
First of all, I guess you plan to not run more than 5 companions at a given time (only if you notice your oponent doesn't seems to run crow control) cause Enquea is specially dangerous against your 3 vit companions. I know that Sam is only there against corruption and pip can land on table, do his job and then die for the badest minion around, but 6 comps is always a threat.
I would start
Grimbold instead of Arwen (or Theoden) and add another simby to grab companions and possessions faster. You can get advantage of his text since the beggining.
Theoden, TaP is a nice companion to start with him so you can kill him at first sites to play another nice companion after fellowship phase (but that would make you add more copies of Arwen) or keep him and discard extra companion in case you got it soon (like
Elfhelm who get stonger at later sites). That way a big minion at first sites will not ruin your day and you can keep Theoden naked util last sites. If you go heavy on plains why not add another
swift steed instead of
Brego? That horsies can save your life against damage + minions, or prevent auto death against events like
Red Wrath and Mordor Strenght. For healing i suggest
Leowyn instead of MoN. She keeps at table and its a guarantee one (or two in extreme cases) heal that stay at table (few shadows have ally hate).
My deck originally runs the best card ever for valiant companins:
Let us be Swift ! 2 condition and one site doesn't seem bad at all! I would put them instead of
FNF and
FDA in case you decide to run Theoden, that way you doesn't rely too much on conditions to do your site liberation and condition discard. I would remove extra copy of
Asfaloth and
Gwemegil to add another 2 copies of Arwen if you don't start her.
I would add another Arrow-Slitz in the place of
Armory since you don't have Gandy to do the job with
Roll of Thunder.
I remember even that Third Marshall is so awesome i didn't run run, and played with the valiant Eomer (the one that discard cards to pump or the st 8 one) and replaced
firefoot for another swift stead, just to make sure i will have the valiant people around, but i guess stick with Third Marshall and his horse is also a good option (since you don't have to many pumps)
To sumarize i will do this:
Adds:
-
Theoden, TaP +1 (and start him with
Grimbold)
-
Let us Be Swift +2
-
Swift Steed +1
-
Arwen, QoEaM +2 (extra copies heal her while
Leowyn heals your rohan fellows)
-
Leowyn +1
- Rider Spear +1
-
Simbelmyne +1
-
Scroll of Isildur (better one bird at hand than 2 flying) +1
- Arrow Slitz +1 (belive you need to get rid of corsairs boats and grond as fast as possible!)
Remove:
-
FNF -2
-
Brego -1
-
FNF -2
-
Fell Deeds Awake -1
- Eomer Spear -1
-
Pippin, HosI -1
-
Phial of Galadriel -1
-
Armory -1
That makes you on 36 cards, but with 4 simbys,
Leowyn and Grimold helping on cycle i think your deck will still running smoothly.
Of course if you lose 2 valiants companions you will be lost but maybe it worth a try.