I posted about this in the CE Thread waaaay back on the old IG forums, but I still think one of the best in-box tchotchke's ever was the manual for the Crimson Skies flight simulator, which was written as a magazine called Air Action Weekly. Everything about it played up the 30's pulp-era feel, especially because the thing was actually printed on pulp paper. Now Crimson Skies didn't have a CE, but it was my favorite example of having something literally in the box that started telling you the game's story before you even started playing the game.
I agree with watchman about a map of Columbia presented as something like the map to Disney World or Great Adventure. Having a map could be cool because it can serve to foreshadow locations in the game before the player has the chance to experience them in gameplay, which is a nice way of unobtrusive storytelling.




