It's not such an easy question Lar asked there.... I'd say it depends on the game. Generally I'd go for the first option:
Lots of levels with each level being very different, connected through a map a.k.a. Baldur's Gate or Fallout
The levels shouldn't be too small of course and the loading time should be very short. I'd prefer such an approach because with those huge worlds, I tend to feel overwhelmed lately. I mean, it's nice of course that the game worlds grow and grow but if the whole game turns into a schedule planning simulation in which you have to use a huge Excel sheet in order to know what to do where... it's not what I would call a great game.
I used to be a great fan of freedom of actions in games... however, I changed my mind partly and would prefer a game with a compelling story and a very visible main storyline. Of course the player should be able to do what they want and not follow the main story, but honestly: Who plays those games for weeks and months without caring about the story? Not many, I'd say... a few only compared to all the people who buy games like Oblivion or Gothic 3 for example. Personally, I am too old and don't have the time to excessively play a game for weeks... that's why I'd like to play a game which provides concentrated fun for the player. It's the developers' job now to make such a game - leading the player through the game along the storyline but also giving them the freedom to do a bit more if they want.
I think the level approach would be the best in that matter.