Ico & Shadow of the Colossus are my favourites.

And the Half Life & Portal series.

Portal 2 did a masterful job of this. The characters' dialogue and the environmental cues meshed together like a well-oiled turret.

The best example I can think of (if I got the concept right) is the Myst series, especially the first two games.

You're given little to no information about the worlds (not even in the manual) and bits of dialogue are few and far between. Most of the backstory are pieced together from observation of the game environment.

I like Dark Souls, Demon's Souls and their sequels for this. Broken environments combined with item descriptions can tell a beautiful(ly horrific) tale.

Spec ops the line, gives an insight into Walker's mental state. He sees what he wants to see.

And Sachys wins the thread.

Funny too since I just picked up Roadside Picnic :D

Vault 11 in Fallout: NV period.

Not exactly what you're asking for, but cw8's answer reminded me of that moment in Fallout 3 where after a lot of hectic running and hiding (in my case) in narrow corridors, I rushed out of the vault cave in the beginning to....woah
Wide open spaces
Anti-claustrophobia
Total freedom to go in whichever direction I want, with no corridors

Was quite a little moment they set up there (probably quite intentionally, considering the lighting effects and such), but it worked quite well.

I still remember enjoying how the Pride Lands have changed since Scar took over in Lion King. Compared to the first colorful levels the last one looks very grim and dangerous.

Many examples from WoW, which is mentioned.

But Bioshock 1 and 2 does it really well also. Quite a lot can be picked up from the environments alone.

Well uh... Entirety of Dark Souls, obviously :-P

Anyway, favorite examples? There's quite a lot actually. Far too many for me to remember, so I'll just go by whatever I do manage to recall:
There are bits in Dying Light where, during scavenging houses, you can quite plainly see what happened to their inhabitants. Like partially barred doors with a single one left wide open, dead people tucked away at the top floor of a building with empty cans of food, that sort of thing. That's not all tho - Dying Light also tries to construct Harran as a living space by progressively changing parts of the map where you manage to establish Safe Zones - survivors move in and might give you quests, shopkeepers open shops (obviously, that's necessary in a wrecked city), that kind of thing. Now that I think about it, even Witcher 3 did this - refugees moving into cleared bandit camps, believers coming back to offer their prayers when you clear vicinity of shrines of danger, that sort of stuff. It really makes the world feel a lot more alive.

I love when levels change to show a progressive trend - like STALKER where you move from ruined country-side to a town which is miraculously still standing. Or Skyrim where you may start exploring a random cave, which turns out to be an excavation site, then you find this excavation site is connected to a breach in an old dwemer ruin, and then you find that all dwemer ruins are connected by a huge underground cave. Yep, Elder Scrolls games in general are pretty great at this kind of stuff, and it shows you how did the world change trough time without actually having to tell you anything.

Anyway, that's it for now. I'm sure I'll come up with more eventually.

Nice examples so far!

Half-Life 2; "We don't go to Ravenholm". Great chapter where (for those who haven't played it) you get through a deserted (& destroyed) city full of traps laid by a crazy priest and, obviously, headcrabs with their hosts.

HL2 and generally Valve's games are pretty good at this. In HL2, if you see a destroyed encampment and an empty shell, you can bet there will be zombies somewhere around. Created from rebels who used to live there. ... Yeah. And while we're talking zombies, Valve even uses Zombies themselves to subliminally help tell story in Left 4 Dead games - like if you're on a construction site, you can see zombies in construction worker uniforms, probably kinda surprised by the whole apocalypse thing in the middle of their work. You can see minor blockades with zombified soldiers, that kind of stuff. It's really quite cool (of course, L4D does more than that - messages in safe zones, random quarantine barricades, things like that)

Half-life 1 as well. I've been playing it off and on recently and I've actually been quite surprised at how much story there is, that went completely over my head when I played it as a teenager.