Hmmm.... I like the idea of going to a Fencing school( with a Maister of Defence ) to learn/practice fighting styles. Cool.
I don't mind simple quests to go kill trouble makers, get me a wolf pelt as long as it means going some where and looking for one. I guess it's just the abattoir out side the city gates that I object to.
Things like having to use a tracking skill to find the prey (glowing footsteps if your successful in tracking would be cool).
Also why do you have to start so weak? I guess that's just a hang up of DnD. Some way of getting rewarded for doing things inline with your character would be good (not just good characters doing good things), may be a way of selectign from a list of character values in character creation?
Doing quests that help those values progress you doing the opposite slows you down/hinders you. See a pnp game called Riddle of Steel to get an idea of what I'm going on about. Would be very hard to implement well though I think

Being given choices to change during the course of a quest might be cool to. For example one trat you selected at start up could be "Loyalty to King Bob" (NPC) so doing quests he gives out gets you more progression. In one adventure you could find out that he is really evil!! or be offerd lots of money to turn traitor so you could then change that trait to "Loyalty to King Fred" while in the short term this would hinder you, slow done progression, it could also open up a whole new set of adventures from King Fred.
Ok I'll stop my random ideas now

I think that the above might get too complicated to manage but maybe worth thinking about.
dan