What was the entropy of the universe at the time of the Big Bang? (I asked this question in Philosophy.SE; but I was advised to direct it here, despite it is, in my opinion, somewhat too speculative for physics.SE).
High entropy generally means high disorder; and low entropy low disorder; the two paradigmatic cases that illustrate these two possibilities is a gas, for the first, and a crystal for the second.
Since Entropy always increases (in general); its expected that the entropy at the beginning of the universe should be the lowest possible.
Which means it ought to be considered as a crystal.
On the other hand, as the universe is squeezed to something smaller than an atom; one expects the temperature to climb precipitously, and for any structure in matter, and perhaps space and time too to 'melt'; and hence approach the state of a gas (perhaps plasma might be a better description here).
How can one resolve these two possibilities?
Does considering that the singularity is a black hole allow one to make some guarded guesses here?
 A: What I will state is speculative and based on the statistical mechanics derivation of entropy, and just the way I view it and do not consider that there exists a problem. After all thermodynamic theory emerges from the underlying statistical level of atomic and molecular interactions.

where p_i is the probabability of microstate i.
Setting aside quantum mechanics to begin with, General Relativity gives a singularity at the very beginning, one spacet time point. This, counted as a microstate, is 1, with probability 1, since everything is at one spacetime point.  Thus S=0. 
Now we know nature and particularly at small dimensions is quantum mechanical, which means an uncertainty due to the probabilistic nature , which can only be estimated if one has a concrete quantized model of gravity. I expect that the number for the entropy will be small even in that case, at least smaller than the entropy, counted as microstates, for the next stage after the locus of classical singularity is passed.
A: "High" and "low" are relative terms that usually also carry an anthropocentric connotation. What "high" means depends on what humans think of as a large quantity but to thermodynamics the absolute scale does not matter! What matters is only that there is a change from one entropic state to another. As long as there is such a change, no matter how slow, there is a dynamic driven by a thermodynamic term.
What those changes are is given by the phase diagram of the system. Let's look at the problem associated with that: a diamond is a highly ordered state of carbon, but it is by no means the ground state. The diamond phase is obviously not thermodynamically stable, and yet, you can keep staring at a diamond at room temperature as long as you want, it's not going to turn into a lump of coal. That, however, is a consequence of the human timescale, it's not what fundamentally happens to the diamond in the long run: it will turn to coal a long time after all of us have turned to dust. We have plenty of examples of extremely slow phase transitions of this kind. The slowest suspected one may be black hole evaporation. 
So we are facing a couple of tough problems here: for one thing we don't know the actual phase diagram of the universe and even if you knew it, there would be no easy way to tell what time scales phase transitions to a higher entropy state will take! The next phase transition (from the phase of the universe we see, right now) to the phase of the universe that will come next, may very well happen on a time scale of 1e40-1e100 years, or so (if we believe black hole evaporation, proton decay estimates etc.). However, if you look at the time scale of that phase transition from the perspective of a "normal" time scale of the following phase, it may happen in an instant... or as quickly as inflation may have happened on the scale of human time perception. 
This argument can be strung out at infinitum and it basically isolates every phase of the universe from the next by an abyssal time scale. 
A: The low-entropy initial state of the universe is an open problem without a satisfactory answer.  Your question is the first time I've heard the suggestion that the initial state should have been a crystal; you remind me that the quark-gluon plasma, which was the state of the universe while it was too hot for nucleons to be stable, has been shown to be a minimum-entropy fluid.
Sean Carroll wrote a nice book on the subject a couple of years ago, which I think was an extension of this paper.
A: 
the two paradigmatic cases that illustrate these two possibilities is a gas, for the first, and a crystal for the second.

Paradigms and examples are well and good, but be careful not to assume they are the only possibilities. In particular, black holes have entropy -- a lot of entropy. In fact they saturate the Beckenstein Bound.
The entropy of a black hole is given by
$$ S_\mathrm{BH} = \frac{k_\mathrm{B}A}{4\ell_\mathrm{P}^2} = \frac{\pi c^3k_\mathrm{B}R_\mathrm{S}^2}{G\hbar} = \frac{4\pi Gk_\mathrm{B}M^2}{\hbar c} = 5\times10^{76}\ k_\mathrm{B} \left(\frac{M}{M_\odot}\right)^2. $$
Supermassive black holes in galaxies' centers range in mass from about a million to over billion solar masses, so each one contributes something like $10^{88}{-}10^{95}\ k_\mathrm{B}$ of entropy.
For comparison, consider the entropy of the present-day CMB. With an energy density $u = 4\times10^{-14}\ \mathrm{J/m^3}$, at a temperature of $T = 2.7\ \mathrm{K}$, in a volume of radius $c/H_0 = 1.3\times10^{26}\ \mathrm{m}$, the entropy of this black body photon gas is
$$ S_\mathrm{CMB} = \frac{4u}{3T} \cdot \frac{4\pi}{3} \left(\frac{c}{H_0}\right)^3 = 10^{88}\ k_\mathrm{B}. $$ As it turns out, star light and any non-relativistic particles contribute negligible amounts of entropy compared to $S_\mathrm{CMB}$ (indeed the temperature of the universe's non-relativistic hydrogen is irrelevant, "hot" though it may be).
One present-day supermassive black hole can have orders of magnitude more entropy than all the gas and dust and radiation in a 14 billion light year radius.

Since Entropy always increases (in general); its expected that the entropy at the beginning of the universe should be the lowest possible.

This is a logical fallacy. From the premiss "entropy always increases," we can derive the conclusion "the entropy at the beginning of the universe was lower than it is now." We cannot from this one premiss say anything about the absolute entropy back then. In particular, there is no reason it need be close to zero or a minimal value in any sense. Is simply cannot be maximal.
A: In the early Universe, entropy is preserved (dS=0). This comes out of the equations of general relativity, but it can be also understood by thinking in terms of classical dynamics: the Universe is a closed system, no heat is exchanged when expanding, so its entropy must not variate.
