The question says melting point not boiling point BTW.
It is actually very relevant to make the distinction between boiling points and melting points. There are quite a lot of things that can happen with the boiling points of binary mixtures, which depend greatly on what the two compounds are and in what concentration. For example the compounds could boil independently from one another, or form maximum or minimum boiling azeotropes.
As for melting point
on the other hand, you're right that it will be depressed. One explanation that I've heard is that because the two compounds are of different shapes (and size) the crystal structure of the mixture will not be as tightly packed as for each of the pure compounds. They just don't stack together as well. This irregular packing reduces the overall intermolecular forces keeping the solid together, and it melts at a lower melting point. Which is basically what you said, but referring to solids instead of liquids.
Keep in mind, though, that his explanation hinges on the two substances being different enough in shape (and size). When talking about metals
, for example, this isn't always the case and things get more complicated. Metals can form what are sometimes called substitution alloys
where the melting point can actually be much higher (Copper-Nickel alloys can do this, for example). They can also form eutectics
where the melting point is much lower (an example of an eutectic would be solder, which is tin and lead I think)