It depends on the game. For your basic shooter, I'm quite fine with the linear "Go from A to B and kill everything that isn't human, occasionally stopping to blow something up, stop something from blowing up, or get in a tank to blow shit up" style of Gears and Halo, but I do enjoy open-worldy "Do as you please" games like Saints Row 2, Oblivion, or Fallout 3. I'm also quite fine with games that mix it, provided it's done well, like KotOR or Mass Effect (my only qualm with ME is that there all the random planets are just 'land, kill some stuff, find some stuff, leave'. The only civilized place ever worth visiting is Noveria and the Citadel. There should have been way more colonies and the like for you to visit. ).
Also, that Mount&Blade game is very interesting looking.