It has recently been pointed out that if the surface tension of quark matter is low enough, the surface of a strange star will be a crust consisting of a crystal of charged strangelets in a neutralizing background of electrons. This affects the behavior of the surface, and must be taken into account in efforts to observationally rule out strange stars. We calculate the thickness of this ``mixed phase'' crust, taking into account the effects of surface tension and Debye screening of electric charge. Our calculation uses a generic parametrization of the equation of state of quark matter. For a reasonable range of quark matter equations of state, and surface tension of order a few MeV/fm^2, we find that the preferred crystal structure always involves spherical strangelets, not rods or slabs of quark matter. We find that for a star of radius 10 km and mass 1.5 Msolar, the strangelet-crystal crust can be from zero to hundreds of meters thick, the thickness being greater when the strange quark is heavier, and the surface tension is smaller. For smaller quark stars the crust will be even thicker.