Fittingly, Théoden has been the lynchpin of Rohan decks since his release. Rohan decks have never really reached the lofty heights of power attained by Dwarves and others, but they remain popular, and the arrival of Théoden marked the beginning of something of a Rohan renaissance just as Gandalf arousing Théoden's fighting spirit led to a revitalising and return to glory of the Rohirrim.
Statistically, Théoden is fairly imposing. Strongest on , but also a good quester and while ideally you might like an extra point of or at least an extra hit point, Sentinel is always potentially useful. His combat abilities can be boosted on both fronts with the thematic choices of Herugrim and Golden Shield (or others if you don't care about theme), and he also has his own action advantage available in Snowmane (though again, other options are available).
So as we can see, Théoden can work very nicely as a hero powerhouse, but his ability also helps you bring in useful allies by making them cheaper. Assuming you have a steady stream of Rohan allies running through your hand (admittedly this can be hard to maintain as Rohan lacks good card draw) then Théoden's ability essentially provides you with an extra resource every round, a very powerful benefit. Particularly relevant for Rohan though because the Rohan allies have a big theme running through them of discarding them for benefits, whether it be innately like Escort from Edoras, The Riddermark's Finest, Háma or Riddermark Knight; or through other effects like Ride to Ruin or Helm! Helm! If you're discarding your allies on even a semi-regular basis then being able to cheaply replace them is very important. Of course now with cards like Gamling and Gúthwinë you can repeat the same allies you just discarded, and this does help solve the problem of ensuring you always have allies available to play, but whether you're replaying the same allies again or replacing them with new ones you still need to be able to afford them and that cost reduction every round from Théoden becomes a big deal. The ability to turn Théoden into a powerhouse hero with a stack of attachments can also lessen the problem of your allies being inconsistent.
It's certainly possible to build a Rohan-themed deck without Théoden. For one thing there's always the option of abandoning the allies and focusing purely on heroes, perhaps with Mounts and Elfhelm. But if you are building a deck with a focus on Rohan allies, then not only is Théoden an exceedingly good hero choice, it's very hard to justify leaving him out. The Rohirrim need their king.