PCs? Personal Computers? That would make for an extremely original game
...I think Anduril Flame has some good ideas. I think the recurring evil character should be a ringwraith, like the witch-king, or maybe the mouth of sauron. I don't know the rules of D&D, but I suppose it could also be a small band of orcs, lead by a notable captain, who get picked off one by one at each encounter, until only the captain remains.
Another significant detour could be the player characters being caught and brought to Isengard, then having them escape, take refuge in Helm's Deep, where a battle could take place, then finishing their trek to the Shire.
Or maybe they could arrive at the Shire and find out that Bilbo went on another adventure, and that they have to follow him.
I'm just throwing some ideas out there... sorry if they're of no use