I'm also really enjoying the game, but as Russ said, the storyline really doesn't seem to leave much 'breathing room' for exploring the city. Unless, of course, you deliberately ignore what you're supposed to be doing.
In GTA, and most other 'open world' games, you get a mission from someone, do the mission, and then you're back in the open world to explore until you choose to go get your next mission. In Mafia II, you always have a plot-related objective to meet, and missions are frequently bookended by chapter changes/cutscenes.
On another note, the game (PC) is almost perfect if you have a 3D-capable display. Other than a few minor issues with some reflections or other light sources it has worked perfectly, and the immersion level is incredible. It's the first full game I've been playing through since I set up my 3D monitor, and it's a very nice experience.