Why do you think there is such a big difference in the solubility of different solids in water?

The crystal structure of the solid differes in the energy necessary to break the bonds of the crystal lattice and the heat of solution of the solids difffer. Some solids dissolve as an endothermic process in which case the entropy of the system increases enough to overcome the other forces.