Here are a few games that I have thoroughly enjoyed. You will have to check the ratings of them, but they are not that bad at all.
Red Faction: Guerilla (Has completely destructible environments. The physics in this game are so much fun)
Mass Effect
Borderlands (This game isn't extremely violent, but it is more of a stylized violence. You should check out some videos. I liked it a lot.)
The Orange Box (This disk has all of the following games on it: Half Life 2, Half Life 2: Episode 1, Half Life 2: Episode 2, Team Fortress, and Portal.)(Now, the Half Life games do have blood in them, but disregard it. When you play it, it will be one of the most immersive and story/character driven games you will ever play. Trust me, you will love it. Also, Portal is an absolute blast)
Edit: Wow, just checked the ratings and they are ALL rated "M". I think though that you should just look past the rating. There are some games that deserve an M rating (Like Gears of War), but some (Like Halo or Half Life) don't really deserve and M rating. A game gets an M rating if there is any blood when you shoot someone. That is really it. All the games above have blood, but when you start playing and listen to the story, you kind of overlook it. (Except for borderlands, sometimes people explode
)