I've been following Dreams in the Lich House's Cthulhu sandbox posts with interest, since the idea has been kicking around in my head for a while now too. (I'm a lazy blogger, though.) The sandbox I picture is something halfway between what I imagine most (good) Vampire games are like—politicking, favour-mongering and investigations punctuated by unexpectedly violent responses—and Pelgrane's excellent Armitage Files campaign-in-a-box kit, which Dreams mentioned a few times. He adopts the term 'target-rich environment' for the idea: lots of clues toward lots of concurrent mysteries and suggestions for a player-directed exploration of the environment.
I want a place which has what every D&D adventure area has: dangerous subterranean locations (like 'The Haunting'); dangerous wilderness locations (like 'A Night on Owlshead Mountain'); a 'home base' with different societies coexisting (or not coexisting, as it were); a source of hirelings and new PCs (like the Silver Twilight or Delta Green), either from local sources or people just passing through; a bunch of people out to make a buck; and vicious calumnies plus a hint of horrible truth about each of them (like the Necronomicon).
So, as a starting point, here's my not-so-short list of places:
West Virginia has always struck me as a spooky and occasionally terrifying place, not just because of their patron ultraterrestrial. It's also because of guys like these and those miniature corporate dictatorships which seem to spring up whenever profit and desperation intersect. The terrain adds to that feeling of isolation, shoving all the urban areas into tiny strips along rivers and piling the natural spaces right overtop of them, a physical reminder of the wilderness and wild people just hidden behind the treeline. Aside from the Mothman film adaption and Matewan (filmed in a town that looks almost exactly like it did in the 1920s), film adaptions tend to focus on the deadly hillbilly attacks angle, so I don't feel I have a good, well-rounded sense of what the place is like.
Mythos Connections: Despite sounding like a state-sized version of Dunwich, and the aforementioned extradimensional wildlife, none that I'm aware of.
Louisiana doesn't need an explanation. If you're talking about the best places to set a horror story in North America, it's a given. Unlike West Virginia, the Spooky Louisiana backdrop is almost over-supported, from Alan Moore's excellent Swamp Thing run to, again, Vampire, to the Haunted Mansion ride.
Mythos connections: Legrasse's tale in 'The Call of Cthulhu,' the scenario 'The Plantation' in Mansions of Madness (set in Carolina, I think, but who remembers that?), another swampier scenario, 'Murder of Crows' in Mortal Coils, and a whole sourcebook, Secrets of New Orleans.
The biggest recommendation for Toronto is that I live here. I'm not sure I can summon up the devotion Lovecraft had for his native Providence towards my particular native burg, but there's particular times and places—the high garret of Casa Loma; Honest Ed's in winter; Queen and Bathurst in summer; deserted (or at least run-down) shops between King East and the lake; the Don Valley from the subway at sunset—where there's deep-rooted sense of familial affection.
The very mundanity of the setting is a strike against it, though. Methodist Rome's self-image makes it hard to really believe places like the Ward really existed, much less in the middle of what is a grey, Modernist—even Brutalist—corridor of the city. Toronto now is defined by Videodrome and Twitch City—but digging into Toronto then to find something sordid and gothic enough to hang stories on is a little harder. Creating my own Canadian Arkham might be a better bet.
Mythos Connections: None that I'm aware of; the city's only appearances in Call of Cthulhu scenarios I've read are set in the modern day, and don't feature any native entities.
Feeling unsatisfied by the North American locations that come to mind, I could go for British colony somewhere warm. Imperial Britain is still a powerful image in the Classic era, something we're still familiar with now.
Cairo is a good starting place. It's filled with the detritus and folly of empires new and old, winding streets and winding catacombs. Really, I don't think it needs to be sold. The downside to that is less opportunity to pin down details of my own.
Mythos Connections: All of them. Specifically, the Cairo chapter of Masks is all you'd need to actually run it.
My next thought is an island territory off Southeast Asia: Papua New Guina, Burma, Borneo, or some other bit between the Pacific and Ceylon. I don't actually know as much about the geography or history of the region, so there's a greater weight of research for setting a game here. The fact that I can't even pin down a specific island probably means I wouldn't be able to do it justice.
Mythos Connections: To vague to say. You could throw in the staples of Tcho-Tcho, deep ones, and Mu, or plant something in the soil of local myth and folklore one a specific site is chosen.
Shanghai, another traditional Call of Cthulhu location, (not to mention pulp literature staple) is also an obvious choice. Like other pulp staples, it's a city of stark contrasts between wealthy and poor; rural natives, cosmopolitan urbanites and foreign visitors.
Mythos Connections; Like Cairo, it's chapter from Masks gives you plenty of starting points and culty doo-dads. It's also the eponymous setting for 'Shanghai Bullets,' one of my favourite ToC scenarios and one which gives you plenty of reusable NPCs as fodder.
Aden, the Protectorate's hinterland, and the Kingdom of Yemen is less well-represented in Call of Cthulhu adventures, but the area's claim to mythos prominence is Sana'a, the birthplace of Abd Al-Azrad himself. It's not too far from Irem of the Pillars and the Nameless City, either. Explicit mythos connections are just two or three disparaging lines in Tatters of the King. Physically, the city of Aden is located in an extinct volcano jutting out into the Indian Ocean. It's a stopover point for mail and travellers going from Europe to the Raj, putting it in the middle of what was a real-world occult pilgrimage. Like Shanghai, there's a big difference between the rural, tribal hinterland and the internationally-flavoured urban port.
Aden was my first choice for a while, but after trying to dig up some more research I hit a wall trying to figure out what it felt like in the Classic era. I have some detailed descriptions of the city's role in international politics of Empire, but I couldn't tell you what the number of reported homicides in 1932 were.
Next time on The Elder Skull, we travel farther afield in search of exciting cosmic horror-cosmopolitan convergences…