WHOA Fellowship Quest! I played that long ago. I always hated that if you died, you were out of the game permanently. And other stuff like with how hard it was to find a game being hosted for it, resulted in the Game Over's being horrid!
I think you should really up it by adding the Cinematic Dialogues with NPC's! Where you can go up to an NPC and speak to them! Start with 2-3 lines per NPC! I don't think the game had that many NPC's if I remember correctly, as in like the friendly ones.
If you want to go further, you can customize the stat system beyond just Strength, Agility, Intelligence. Lots of maps used to rename the stats, and even change what they do. Sometimes they renamed Mana to Energy, or Wisdom, etc (you can do it in one of the built in Modules, like Game Rule Editor or something, it's got tons of options to play with). Hero Line Wars even had it so you could press Escape, and it would bring up a Stat input menu! You could put in your Stat Points into Strength, Agility, etc.
You can even try to get cool weapon attachment models, and attach them to different characters at different points. Like maybe even upgrade Legolas' daggers at some point!
Other cool things would be if we get some environment exploration, like pretty waterfalls, nice skylines, nice lush trees (there's tons of cool tree models here), and it would be MEGA WIN if we could swim in the water!