We have conducted a high signal-to-noise spectroscopic survey of 670 nearby early-type stars, to map Diffuse Interstellar Band (DIB) absorption in and around the Local Bubble. The project started with a Southern hemisphere survey conducted at the European Southern Observatory's New Technology Telescope and has since been extended to an all-sky survey using the Isaac Newton Telescope. In this first paper in the series, we introduce the overall project and present the results from the Southern hemisphere survey. We make available a catalogue of equivalent-width measurements of the DIBs at 5780, 5797, 5850, 6196, 6203, 6270, 6283 & 6614{AA}, the interstellar NaI D lines at 5890 & 5896{AA}, and the stellar HeI line at 5876{AA}. We find that the 5780{AA} DIB is relatively strong throughout, as compared to the 5797{AA} DIB, but especially within the Local Bubble and at the interface with more neutral medium. The 6203{AA} DIB shows a similar behaviour, but with respect to the 6196{AA} DIB. Some nearby stars show surprisingly strong DIBs whereas some distant stars show very weak DIBs, indicating small-scale structure within as well as outside the Local Bubble. The sight-lines with non-detections trace the extent of the Local Bubble especially clearly, and show it opening out into the Halo. The Local Bubble has a wall which is in contact with hot gas and/or a harsh interstellar radiation field. That wall is perforated though, causing leakage of radiation and possibly hot gas. On the other hand, compact self-shielded cloudlets are present much closer to the Sun, probably within the Local Bubble itself. As for the carriers of the DIBs, our observations confirm the notion that these are large molecules, whose differences in behaviour are mainly governed by their differing resilience and/or electrical charge, with more subtle differences possibly related to varying excitation.