Two of my favourite games in the last few years have been Far Cry 2 and GTA 4. I've now been playing Mafia 2 for a week, and it strikes me that all three have a lot in common. Obviously, as single-player games at least, they are mission-based, open-world action games with lots driving and shooting. They were also all received with a significant amount of criticism, and much of it I believe was based on what you do between the meat of the missions.
Each game has chosen to try to be more than just a series of gunfights, and to try to bring you into the world of the characters depicted, and though each has cut-scenes, they've done this primarily by utilizing the quiet times between mission.
Interestingly, I've read criticism of the driving sections of each, for being too frequent and repetitive, and for bad handling, but I think this is deliberate. Where Heavy Rain has you doing dishes and brushing your teeth, then games have you commuting almost, in an attempt to get you into the mind of the character, and to keep you immersed in the atmosphere of the world.
There are significant differences between each game though.
Whenever I recommend Far Cry 2, and I do still, I always have to give a warning like "but you must slow down to the pace of life in the game, absorb the atmosphere". These games cannot be rushed, but I don't think they'd be as immersive if they could be.
As a counter-example, take Half Life 2. (Risky to compare anything to this paragon, I know, but hear me out.) I enjoyed the story, liked the characters I met, both major and minor, and got to know the world I was in. However, I never found it immersive, probably because Gordon and me never had to actually live in it. It was just a series of missions.
I never had this problem in Far Cry 2 or GTA 4. I don't think that's just because Half Life 2 was on rails, though that's part of it. It's not just that you can't choose your route or missions, it's that you don't live the life at all.
I haven't argued it here, but I think that immersion is a wonderful thing for a game to achieve, and that immersion is achieved by the player having to live in the character's world. If you're going to simulate life in such game worlds, the most important elements are the game mechanics outside the missions. Driving is one of the easiest to get right. (Other examples might be walking, visitting gun shops, and reloading.) Arbitrary activities, like choosing clothes, and mini-games are less effective, I think.
So next time you're playing and thinking "Oh no, other side of the map again", relax into the drive, and later on think about whether a little slow time in real life actually drew you into the game world.