Here is my take on a thematic Rohan deck, focusing on the Marshals.
Its not as optimal as it could be with a few other cards (Celebrian's Stone, for example) but I wanted to keep with the Rohan theme. Gandalf is a concession because I kept either threating out or I needed cards early and well, he did ride with Rohan once or twice. I may try using Hobbit Gandalf with Shadowfax to get extra willpower. I'll also update it with the newer Rohan cards of the cycle as they come out.
The basic strategy is to use the in-and-out play of the cards to power Eomer and indirect questing. Firefoot and Spear of the Mark go on him to get him to +8 attack. I found Hour of Wrath a better card than the typical build with Rohan Warhorse to get him (and others late game with Valour) action advantage.
A Good Harvest is there to get Gamling in as early as possible. I've used various combinations of the Rohan allies and events and this seems to be most consistent. I also tried the deck with Herugrim, but I found it cost prohibitive for what I was getting. This iteration can struggle without healing and sometimes it can stall if you don't get allies out.
You are not going to win every scenario, but it is decently competitive and more importantly, thematic and a lot of fun. I welcome suggestions!