You are right in that we need to assume that the universe started in an extremely small entropy state. This is basically the past hypothesis. (Which can be justified to some extent using anthropic principle and eternal inflation, however these two ideas are very controversial among physicists.)