Another good example is Deus Ex, and yes, I wish for the same thing. More freedom within missions.
GTA IV actually did this, though. Many of the later missions (specifically the ones in Alderney) give you alternate routes and even show you them before the mission starts. There's one mission in particular where you have to blow up a bunch of parked vans, and you can either climb up and snipe everyone from above, lob grenades in the garages or just run in guns blazing. Another mission, the one in the abandoned hospital, has a little boat hidden in the back you can escape with, or fight your way through the NOOSE to do a car chase.
I'd still like more though. It'd be great if instead of failing out of missions, you just complete them in a way that opens up alternate missions, or mixes the order, or something like that.