Softness and hardness has nothing to do with the physical hardness of an element. Elements with higher electronegativities (like oxygen) have smaller orbitals with more concentrated charges and are classified as hard. Elements further down the periodic table have larger, more diffuse orbitals and are less electronegative. That's why orbital interactions are more important for these elements than electrostatic interactions for the hard elements.
Generally you can say: hard likes hard and soft likes soft. That is why a hard nucleophile such as MeLi adds to a hard electrophile such as a carbonyl carbon. If you however, have an alpha,beta-unsaturated ketone and you use a softer nucleophile such a a cuprate you get a 1,4-addition because the [Me2Cu] species is softer dan MeLi.
One of the reasons gold binds so good with sulpher is because they are both (very) soft elements.