We develop a theory for the proximity effect in superconductor-semiconductor-normal-metal tunneling structures, which have recently been extensively studied experimentally, leading to the observation of transport signatures consistent with the predicted zero-energy Majorana bound states. We show that our model for the semiconductor nanowire having multiple occupied subbands with different transmission probabilities through the barrier reproduces the observed "soft-gap" behavior associated with substantial subgap tunneling conductance. We study the manifestations of the soft-gap phenomenon both in the tunneling conductance and in local density of states measurements and discuss the correlations between these two quantities. We emphasize that the proximity effect associated with the hybridization between low-lying states in the multiband semiconductor and the normal-metal states in the lead is an intrinsic effect leading to the soft-gap problem. In addition to the intrinsic contribution, there may be extrinsic effects, such as, for example, interface disorder, exacerbating the soft-gap problem. Our work establishes the generic possibility of an ubiquitous presence of an intrinsic soft gap in the superconductor-semiconductor-normal-metal tunneling transport conductance induced by the inverse proximity effect of the normal metal.