As my buddy Steve and I wondered around the Independent games section at the GDC, we came across an interesting title that he wanted to check out.
As he was tinkering with the game, he was approached by the kid who had developed the game. Steve didn't want him to tell him anything about the game, becuase he felt he should be able to expirament with the mechanics to learn how to play the game.
I feel a little differently about this.
When I pick up a new game, I want to quickly learn the mechanics so I can play the game. I personally don't want to have to expirament and find out what the developer has formed the gameplay to be.
I personally prefer an level objectives approach.
Give me some objectives that allow me to use the game mechanics to solve them. I need goals as a player to guide me through the game and assure that I get the best experience out of it.
If i'm just given a sandbox to play with, then I may never see the truly fun parts of a game.
To clarify, I like pure discoverability with the sort of 10-20 minute casual games that we were looking at.
Deeper games such as OSW, HL2, Godfather, etc. definitely require tutorials of some kind, preferably masked through stepped goals like you recommend. :)