Another great game for that was Skyrim. But both of these games are as close to true open world as one can get. And they are single player deals.
Heh - whenever I log into Skyrim, I get so lost and unsure of what to do, I go look at some mammoths then log out again. It's almost too big and open...