It depends on what the goal of the deck is.
Theoden, Tall and Proud is somewhat of a must, he is too good. When he dies, he brings back another dude.
Rohirrim Army is nice as well, especially combined with either Theoden or Ketties prevered Red Arrow, since you can safe an other companion from getting hurt. Bye bye Sauron, Witch-king, or what ever minion you might find threatening, or annoying.
Gamling is used also, for his obvious ability to play things in skirmish, not only denying twilight during the fellowshipphase, also giving him the extra 'umpf' he might need to kill whatever waits for him. For a short period of time, he can be your personal Durin.
Eowyn is also a character worthy to take in observation. I myself have -imho- a quite brilliant deck that resolves around
Restless Maiden where she discards her blade to play it again either from hand or with Merry's text to deal another wound. I find it very nice to play. Other choices can be the obvious
LoI, where she is able to kill of minions with a simple exertion and another, much played Eowyn is the one where she can exert to prevent a comp of taking a wound. Somesort of Enquea protection, which is nice. Oh and in movie, I find
TMoR indeed the prefered Eomer to ride with.