The trouble with the set 4 starters is that Aragorn kills Uruks as he's strength 12 with sword, but Rohan is stuck at strength 8 without pumps, so can only beat one minion in the deck. (I'm going for the proper starters here, not the online versions.) But then the Dunlandings die to the Legolas one from BoHD, being totally unable to survive to the skirmish phase and the Uruks from Theoden's deck do a number on those Elves.
I find that Gandalf vs Boromir in WotR is the best matchup. Very evenly matched, with mind games for the Hobbits trying to waste all the
Stragglers Tokens. Get it right and you win, wrong and it's game over. On the other side, even with
Buckland Homestead (worst site ever after
Steward's Tomb) messing up your conditions, Boromir can hold his own against the Nazgul, but it's not a piece of cake at all.
Merry vs Pippin from King block is fun, too!