Play the same map again, and it's somewhere else. Or not there at all.

Left 4 Dead (Valve, 2008) puts its bosses on the map when the map starts. Valve's Michael Booth laid it out in his 2009 talks: along the "escape route", the shortest way from the start safe room to the exit, a spot is marked "every N units" plus or minus a random amount. Then "Three Boss events are shuffled and dealt out: Tank, Witch, and Nothing." One more rule: "Successive repeats are not allowed (ie: Tank, then Tank again)".

Fixed spots get learned, and they remove the "suspense of not knowing what will happen next", as Booth's slide puts it. Pure dice could stack three Tanks together or leave a map with none. The deck sits in between: in Booth's words, "Not purely random, nor deterministically uniform." And the goal, on the same slides: a game played as "a skill challenge instead of a memorization exercise."

The city, the figures and the dice in this film are our own simplified version, built in code from Booth's slides. Booth gives no spacing, so ours is our own; the first deal on screen is the strip on his slide, and how our deck reshuffles is our reading of it. Not affiliated with or endorsed by Valve.

Which other game deals its surprises like cards?

Sources: Michael Booth, "The AI Systems of Left 4 Dead", Valve, AIIDE 2009 (slides 53, 54, 58, 64, 74); Michael Booth, "Replayable Cooperative Game Design: Left 4 Dead", Valve, GDC 2009 (slides 53, 63, 64); valvesoftware.com/en/publications.
Sounds: our own, made in code.