I think that the best way to justify the logarithm is that you want entropy to be an extensive quantity -- that is, if you have two non-interacting systems A and B, you want the entropy of the combined system to be
$$
S_{AB}=S_A+S_B.
$$
If the two systems have $N_A,N_B$ states each, then the combined system has $N_AN_B$ states. So to get additivity in the entropy, you need to take the log.
You might wonder why it's so important that the entropy be extensive (i.e., additive). That's partly just history. Before people had worked out the microscopic basis for entropy, they'd worked out a lot of the theory on macroscopic thermodynamic grounds alone, and the quantity that they'd defined as entropy was additive.
Also, the number of states available to a macroscopic system tends to be absurdly, exponentially large, so if you don't take logarithms it's very inconvenient: who wants to be constantly dealing with numbers like $10^{10^{20}}$?