Why is the entropy of solidifying solution higher than that of a pure solvent?
1) How do we know the particles in a solution are more separated?


When a solution forms, intermolecular bonds in the solid solute are broken and replaced by interactions with the solvent. The solute is then free to diffuse in the solvent. If the solute molecules still interacted in a highly favorable way they would tend to bond and precipitate out. This is exactly what happens when a solute has a low solubility. 


  2) How do the solvent molecules actually separate the solute particles?


What drives the dissolution process is an overall favorable combination of the change in the energy of intermolecular interactions and motional freedom. This is described by the Gibbs free energy. The solvent provides an environment for the solute to move (diffuse), which increases the solute's entropy, and the solvent forms weak interactions with the solute that make up (perhaps only partially) for the lost interactions when in the solid. In general, there is an enthalpic component (bond-breaking and making) and an entropic component (changes in solute configurational freedom) to the free energy. If the energy of the interactions of a solute with itself in the solid is identical to the interaction energy between solute and solvent in the solution, then the change in free energy is described entirely by the entropic contribution. 


  3) Also, we know that the entropy of solid is less than that of a liquid, so shouldn't the addition of solute particle (which are obviously solid) actually lead to lesser entropy than pure liquid?


The solid particle is no longer "solid" when dissolved, it is in a new state. The entropy in solution reflects the new state of the solute upon dissolution. The solute does not retain a memory of what it was before. At low concentrations, the solute is diffusing with few other solute molecules nearby. The new entropy is not an average over the entropy of the starting states (solid and solvent).

(That is unless you are referring to a dispersion of solid particles, but that is called a colloidal solution and is another matter.)