I can't go with the violence free requirement, but if you want a story-driven game, try The Witcher series (start with 1; #2 is a continuation of the story).
They are based on a compilation of short stories written by Polish author Andrzej Sapkowski, who was an international trade broker before becoming a breakout author, and is now one of Poland's best-known authors.
The Witcher is about a man named Geralt who has undergone rigorous training and some genetic mutation to become a monster slayer, a Witcher. Witchers travel from village to village, hoping to make some coin by slaying any number of supernatural monsters that haunt the people.
The games keep the books' settings perfectly, and there is no right or wrong choices, although you are constantly evaluating your morality and motivations. The games are known for this and each choice has consequences later on down the road.
The games (and books) also cater to a more mature audience, and tell a much darker tale than today's contemporary fantasy (LotR, Harry Potter, WoW)--the storyline deals with racism, genocide, terrorism, rape, and revenge. And there is sex, which isn't so much for titillation as enhancing the believability and authenticity of the games.
If you are looking for something a little deeper than today's mindless violence, I highly suggest TW1 and TW2.
And Good Ole Games (GOG.com) has TW1 for $9.99. Can't beat that for what will be 40-60 hours of rich storyline.