A lot of it depends on the person. Some (most?) people enjoy being spoon-fed the story, and to be honest I can't blame them. On the other hand, I personally prefer having to peice together things myself (assuming there's actually anything there to peice together...).
I think that of the most recent games I've played, Fallout 3 does a great job of doing the latter. Ignore the main story (please), and go exploring the ruins of D.C. You'll find that the game has TONS of small stories scattered throughout the wastelands, but few of them are ever just handed out to you.
For example, one building sets up this great moment where you enter and find a skeletal corpse with two ammo cans around it, but no explanation of what happened. The building itself is infested with feral ghouls. Deeper in the building you find a second skeletal corpse, just outside a small closet, with several ghouls huddled near it. If you search the closet, you find a small note detailing the tale of a guy who's cornered by ghouls and out of ammo, but he knows his friend is coming soon with supplies. In fact, he thinks he hears someone calling his name, and he's going to go check...
Strangely, I felt for that guy (who I'd never met) more than I did for my dad or any other main character.