I'd prefer it in RPG form (think: Final Fantasy, Star Ocean 2, Level of Mana) where you can pick and choose a party for various "missions." (like recruit Cutter, Strongbow, Nightfall for a hunting party)
There are lots of "day to day" missions that you could do that wouldn't be incredibly violent - send Redlance and Ember out to secure the holt and make tricks to keep humans at bay, which could level up Redlance's magic to do various things. Hunting (but overdo it and the tribe scolds you) where battle and skill points could be leveled up, each characters having special "abilities" that would also be enhanced, such as Moonshade's tanning for increased armor and defense points on all members of the tribe, or Leetah, whose healing would only restore say, 100HP (hit points) at the beginning of the game, and more and more with stronger healing spells as the game goes on. Other missions could include fighting Madcoil-like beasts, growing the holt, mini-games with the trolls, hunting, scavenger hunting for various items, and tricking humans.
Can you imagine a cutscene with the quality of the movies in the Square games? It could be done in the animation style Wendy's always dreamed (for those who haven't seen recent video game cut scenes - they can rival films like Finding Nemo and any 2D animated cartoon for quality)
A few years ago I actually wrote the first page or two for what an EQ RPG script could be like, with what the NPC (non-playable characters) would say, what the elves did, what the stats were, but I gave up. My idea then was to adapt the Original Quest into an RPG, but it seemed too predictable.