The Kelvin-Helmholtz instability (KHI) has been observed in the solar atmosphere. Ion-neutral collisions may play a relevant role for the growth rate and evolution of the KHI in solar partially ionized plasmas such as in, e.g., solar prominences. Here, we investigate the linear phase of the KHI at an interface between two partially ionized magnetized plasmas in the presence of a shear flow. The effects of ion-neutral collisions and compressibility are included in the analysis. We obtain the dispersion relation of the linear modes and perform parametric studies of the unstable solutions. We find that, in the incompressible case, the KHI is present for any velocity shear regardless of the value of the collision frequency. In the compressible case, the domain of instability depends strongly on the plasma parameters, especially the collision frequency and the density contrast. For high collision frequencies and low density contrasts the KHI is present for super-Alfvénic velocity shear only. For high density contrasts the threshold velocity shear can be reduced to sub-Alfvénic values. For the particular case of turbulent plumes in prominences, we conclude that sub-Alfvénic flow velocities can trigger the KHI thanks to the ion-neutral coupling.