... Maybe we can give Rohan a competitive deck, without going overboard and making them overpowered...  Simply adding Gandalf and Trust Me As You Once Did is a huge advantage to any deck...
This being the case, there were a couple things I did with the deck, to "nerf" it...
1. Removed Elite Rider. Quite often a base strength of 8. Add a spear and TMAYOD, and it's a beast.
2. Removed Eomer
3. Focused on a little Valiant dynamics as opposed to heavy skirmish support. I think the bonus of TMAYOD + x4 An Honorable Charge would have been almost overkill
4. Decided to pull Gandalf's Wisdom out...having the opportunity to play all of those Rohan possessions for no twilight is a little much.
I've been learning a little more about Rohan culture (and Valiant subculture) in order to try a Rohan/Gondor starter or coupling deck and found some issues that may be taken into account; if so they might modify your deck a bit... 
Regarding to the point you mentioned above:
1. Totally agree, 
Elite Rider is a lame companion that kills or survives many heavy things for almost no cost...
2. We 
could use Eomer after all, as this deck 
might lack a single good fighter (everyone else has 6 strenght with no gametext to help). Actually we haven't really many options for Eomer as we won't use Rare cards (
Third Marshal of Riddermark and 
Rohirrim Captain, steroid-aided versions of 
Elite Rider, are out), so 
Sister-Son of Theoden is the only option 
inside Towers Block. He would help with ally mechanics, but would interfere with the Valiant one as he lacks the keyword (Frodo + Gandalf + 3 Valiant men + Eomer = 
Shotgun Enquea or 
Southron Commander). I'm considering 
Eomer, Forthwith Banished as he has that desired unloaded keyword, and doesn't get strength bonuses from exertions 
a la Elite Rider.
3. There are only 3 options for Valiant dynamics as there aren't Rare cards: 
Let Us Be Swift, 
Ecglaf and 
Sigewulf... the latter doesn't merit any mention, but 
Let Us Be Swift by itself seems enough. With Rare Valiant pulls can be awesome.
4. 
Gandalf's Wisdom would be almost useless as many possession can be played on Theoden/Eowyn in Maneuver phase. Those card slots have more important things to do...
Regarding other points:
I. Your deck lacks 2x 
Severed His Bonds. This point REALLY hurts the assembly of the deck...
II. In contrast to 
Rider's Mount, 
Horse of Rohan would allow combination with other cultures that should be included in later series: Naith/Helm's Deep Elves, plain Rangers and Knights; thus they would 
couple into Mounted Elves (
Feathered, 
Lorien Swordsman), Mounted Rangers (
New Errand, 
Ranger's Bow) and Mounted Knights (
Men of Numenor, 
CotS)... The raised twilight cost shouldn't impact too much due to Eowyn and Theoden.
III. Given the previous point, allies should privilege to aid mounted companions (
Leod, 
Weland) instead of rohirrim (
Hlafwine, 
Guma), for further coupling.
So here's my try:
Frodo, Mr. Underhill2x 
Gandalf, The White Wizard1x 
Household Guard2x 
Theoden, King of the Golden Hall1x 
Eomer, Forthwith Banished (starting)
1x 
Eowyn, Daughter of Eomund (starting)
1x 
Guma, Plains Farmer1x 
Leod, Westfold Herdsman1x 
Weland, Smith of the Riddermark1x 
Wizard Staff1x 
Brego1x 
Herugrim2x 
Horse of Rohan2x 
Rider's Spear2x 
Rohirrim Bow2x 
Hobbit Sword2x 
An Honorable Charge1x 
Let Us Be Swift2x 
Severed His Bonds2x 
Trust Me as You Once Did1x 
Arrow-slits1x 
Well Stored4 Gandalf signets... Valiant Rohirrim merged with 
Trust Me Gandalf, with great coupling potential to Elves and Gondorian guys. 1x 
Well Stored is there as a stand-alone healing card for allies... this is essential for coupled decks as they need less presence of Rohan companions (otherwise should rely on Theoden + possessions, or 
Eomer, SSoT to heal 
Weland and 
Leod)...
This deck has great skirimish and healing potential, thus wrecks an archery shadow (should be paired with 
Hate and Archery). Dies awfully against Easterlings, as the natural course of things...