It's an interesting question. The thing is, as a relatively young form of media and one somewhat constrained by its nature, video games have a fairly difficult time delivering both the rudiments of a story and conflict- the "meat" of most stories, and an essential component of a game- without resorting to violence. Violence is relatively easy to depict, especially compared to, say, diplomacy or architecture, in a way that is satisfying to the player and feels consistent with our expectations.
And, yes, games like Mario and Sonic are violent. They're not Mortal Kombat- there isn't a lot of blood, viscera, snapping bones, and mayhem- but the player is still encouraged to destroy enemies who are portrayed as intelligent creatures, and destruction of same is often an important part of progress, or at least difficult to avoid. Unfortunately, on that account, I can't recommend Braid for the same reason.
Looking through my Steam list, though, there are a few contenders. PopCap has some good offerings, including games like Peggle and Bookworm. World of Goo has already been mentioned. Audiosurf is also an amusing diversion, though honestly I don't tend to play it more than ten to fifteen minutes at a time. AaAaAA! A Reckless Disregard For Gravity occasionally results in the player smacking their point-of-view face-first into a building with an implication of gruesome results, but there's no outwardly directed violence.
If you like adventure games, Strong Bad's Cool Game For Attractive People has a certain amount of slapstick, but no serious injuries or deaths. There's also the Cooking Mama series on the DS and Wii, which some people love, though others seem to detest the mere mention of it (and in truth, it probably has expanded in its franchise a bit beyond the welcome.)