Understanding how the gas environment within molecular clouds influences the properties of protostars is a key step towards understanding the physical factors that control star formation. With the availability of large infrared and sub-millimeter surveys, we can now link observationally the properties of the environment (such as column density and temperature) with protostars in large molecular cloud complexes. The Herschel Orion Protostar Survey (HOPS) is a large multi-observatory survey of protostars consisting of data from Herschel, Spitzer, APEX, and other facilities. HOPS has produced well sampled SEDs of over 300 protostars in the Orion molecular clouds - the most extensive survey of a single cloud complex to date. We discus the recently discovered Herschel--detected PACS Bright Red Sources (PBRS) found in the HOPS survey area. In contrast to the known Spitzer protostars targeted with HOPS, the new sources are undetected or very faint in the Spitzer 24 um imaging, possibly due to very dense protostellar envelopes. CARMA follow-up reveals that the PBRS are likely characterized by dense envelopes and have larger than typical 3 mm fluxes. Furthermore, we observe an unexpected concentration of PBRS in the Orion B cloud, highlighting an unexplained environmental dependence. Taking the entire HOPS and PBRS protostar samples together, we show that the luminosity distribution of protostars varies with environment in within the Orion complex. We find that the luminosity, temperatures, and spacing of protostars in Orion depend on the local gas column density.