Lumo has a long post on entropy that is fairly interesting. Although much of it is a nice analysis, he can't resist setting up and toppling some of his usual strawmen:
Every single person who has ever argued that the low-entropy beginning of the Universe is a paradox neglects a huge body of observational evidence that is accessible to most supermodels, namely observations showing that there is a difference between the past and the future.
That statement well may be true, but are any of the people he mentions actually arguing that a low-entropy beginning of the Universe is a paradox, or expressing doubt that the Universe started in a low-entropy state? Not those I've read. Rather, it's a puzzle which challenges some theories of the beginning, expecially those attributing the beginning to a spontaneous fluctuation.
This puzzle is closely related to our friend The Anthropic Principle. We can imagine many possible initial states for the Universe, so why did it just happen to be in a freakishly low entropy state? Just lucky? Some Anthropicy at work? Or, as Penrose has argued, maybe it's a hint at a deep law that prescribed a low entropy beginning and perhaps many other interesting things. The same sort of thing occurs in other contexts. The myriad (ok, not quite that many) seemingly arbitrary parameters of The Standard Model just happen to have values which permit this conveniently (but barely) liveable Universe we find ourselves in. Among the many possible vacuua permitted by string theory, string theorists tell us that one was selected with just the hand properties to lead to our World.
These cosmic coincidences are, as I say, not paradoxes but puzzles - puzzles which may or may not have explanations. For thermodynamics and The Standard Model, these puzzles are interesting, but not a challenge at a fundamental level. Thermodynamics and the Standard Model work just fine and have lots of useful predictive value however the Universe began.
For string theory the challenge is more fundamental. What if string theory is right but there is not preferred state in the landscape? In that case, it's conceiveable that string theory might be unverifiable and unpredictive, because regardless of how many parameters we measure, there might remain myriads of vacuua compatible with them.
As an optimist, I hope that's not the case. I hope that there is more physics out there to be discovered. We, perhaps, shall see.