We show that very large nonlocal nonlinear interactions between pairs of colliding slow-light pulses can be realized in atomic vapors in the regime of electromagnetically induced transparency. These nonlinearities are mediated by strong, long-range dipole--dipole interactions between Rydberg states of the multi-level atoms in a ladder configuration. In contrast to previously studied schemes, this mechanism can yield a homogeneous conditional phase shift of pi even for weakly focused single-photon pulses, thereby allowing a deterministic realization of the photonic phase gate.