Some new stuff. Some older.
Sleeping Dogs - open world Hong Kong crime game with a fantastic story and lots of optional quests to do. Messing around in the city is a blast and you can even grab npcs and throw them into the trunk of your car along with tons of other fun melee stuff.
Far Cry 3 - Huge open world with some of the best stealth and AI that I have ever seen. You'll feel like Rambo silently stalking your prey (both animals and humans) with a whole toolbox of fun weapons. I'm a big fan of the bow, myself. It also has a level editor so you can create your own maps and populate them to mess around in. There is a ton of cool, emergent gameplay that ends up happening, and situations can play out totally differently.
Fallout: New Vegas - Freedom to play however you want, including killing every single npc and having the plot and quest restructure itself to fit your actions. It is more RPG than action, although the gunplay still feels great.
Batman Arkham City - Big open world with tons of optional stuff to do and a great Batman story to boot that's true to the comics.
Lego Batman 2 - Don't laugh. Amazing open world with great missions/story that surprised the hell out of me with how much fun it is to mess around in.
Red Faction Armageddon - Big open world with all sorts of toys to mess around with the architecture. Need to rescue some hostages in a building? Break out your sledgehammer and knock down walls to save them, drive your truck right through the building, or dozens of other interesting ways to approach situations.
Skyrim - Huge and gorgeous open world with tons of little details and things to explore and find. Play however the heck you want. If you use weapons then your proficiency increases with melee, use magic and your spell proficiency increases, etc. You can also do horribly fun things to npcs from stealing/pickpocketing to freezing them and using force shouts to send them flying. One of the more esoteric weapons even has random effects like turning npcs into a sweet roll.
Just Cause 2 - Like SRTT, the game rewards you for causing chaos and destruction instead of punishing. It is one of the most fun open worlds I have ever messed around in, and you can spends countless hours ignoring the main quest and just attaching npcs to your car with your grapple and dragging them around.