Sequence heterogeneity broadens the binding transition of a polymer onto a linear or planar substrate. This effect is analyzed in a real-space renormalization group scheme designed to capture the statistics of rare events. In the strongly disordered regime, binding initiates at an exponentially rare set of ``good contacts. Renormalization of the contact potential yields a Kosterlitz-Thouless type transition in any dimension. This and other predictions are confirmed by extensive numerical simulations of a directed polymer interacting with a columnar defect.