Back in Diablo II, the second you stepped foot outside the Rogue's Encampment, you were in the randomly generated marshes of the Blood Moor.
But my experience in Diablo III has been different - New Tristram, and indeed, the areas surrounding new Tristram seem to be identical for every character I start.
Which areas are randomly generated? Can I tell if I'm in a randomly generated area or not?