Q:

What is the role of the logarithm in Shannon's entropy?

Shannon's entropy is the negative of the sum of the probabilities of each outcome multiplied by the logarithm of probabilities for each outcome. What purpose does the logarithm serve in this equation?
An intuitive or visual answer (as opposed to a deeply mathematical answer) will be given bonus points!

A:

Shannon entropy is a quantity satisfying a set of relations.
In short, logarithm is to make it growing linearly with system size and "behaving like information".
The first means that entropy of tossing a coin $n$ times is $n$ times entropy of tossing a coin once:
$$
- \sum_{i=1}^{2^n} \frac{1}{2^n} \log\left(\tfrac{1}{2^n}\right)
= - \sum_{i=1}^{2^n} \frac{1}{2^n} n \log\left(\tfrac{1}{2}\right)
= n \left( - \sum_{i=1}^{2} \frac{1}{2} \log\left(\tfrac{1}{2}\right) \right) = n.
$$
Or just to see how it works when tossing two different coins (perhaps unfair - with heads with probability $p_1$ and tails $p_2$ for the first coin, and $q_1$ and $q_2$ for the second)
$$
-\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(p_i q_j)
= -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \left( \log(p_i) + \log(q_j) \right)
$$
$$
= -\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(p_i)
-\sum_{i=1}^2 \sum_{j=1}^2 p_i q_j \log(q_j)
= -\sum_{i=1}^2 p_i \log(p_i)
- \sum_{j=1}^2 q_j \log(q_j)
$$
so the properties of logarithm (logarithm of product is sum of logarithms) are crucial.
But also Rényi entropy has this property (it is entropy parametrized by a real number $\alpha$, which becomes Shannon entropy for $\alpha \to 1$).
However, here comes the second property - Shannon entropy is special, as it is related to information.
To get some intuitive feeling, you can look at
$$
H = \sum_i p_i \log \left(\tfrac{1}{p_i} \right)
$$
as the average of $\log(1/p)$.
We can call $\log(1/p)$ information. Why? Because if all events happen with probability $p$, it means that there are $1/p$ events. To tell which event have happened, we need to use $\log(1/p)$ bits
(each bit doubles the number of events we can tell apart).
You may feel anxious "OK, if all events have the same probability it makes sense to use $\log(1/p)$ as a measure of information. But if they are not, why averaging information makes any sense?" - and it is a natural concern.
But it turns out that it makes sense - Shannon's source coding theorem says that a string with uncorrelated letters with probabilities $\{p_i\}_i$ of length $n$ cannot be compressed (on average) to binary string shorter than $n H$. And in fact, we can use Huffman coding to compress the string and get very close to $n H$.
See also:

A nice introduction is Cosma Shalizi's Information theory entry
What is entropy, really? - MathOverflow
Dissecting the GZIP format

A:

This is the same as the other answers, but I think the best way to explain it is to see what Shannon says in his original paper.

The logarithmic measure is more convenient for various reasons:

It is practically more useful. Parameters of engineering importance such as time, bandwidth, number of relays, etc., tend to vary linearly with the logarithm of the number of possibilities. For example, adding one relay to a group doubles the number of possible states of the relays. It adds 1 to the base 2 logarithm of this number. Doubling the time roughly squares the number of possible messages, or doubles the logarithm, etc.
It is nearer to our intuitive feeling as to the proper measure. This is closely related to (1) since we intuitively measures entities by linear comparison with common standards. One feels, for example, that two punched cards should have twice the capacity of one for information storage, and two identical channels twice the capacity of one for transmitting information.
It is mathematically more suitable. Many of the limiting operations are simple in terms of the logarithm but would require clumsy restatement in terms of the number of possibilities

Source: Shannon, A Mathematical Theory of Communication (1948) [pdf].

Note that the Shannon entropy coincides with the Gibbs entropy of statistical mechanics, and there is also an explanation for why the log occurs in Gibbs entropy. In statistical mechanics, entropy is supposed to be a measure the number of possible states $\Omega$ in which a system can be found. The reason why $\log \Omega$ is better than $\Omega$ is because $\Omega$ is usually a very fast-growing function of its arguments, and so cannot be usefully approximated by a Taylor expansion, whereas $\log \Omega$ can be. (I don't know whether this was the original motivation for taking the log, but it is explained this way in a lot of introductory physics books.)

A:

another way of looking at this is from an algorithmic point of view. Imagine that you're going to guess a number $x$, that the only information you have is that this number is in the interval $1 \leq x \leq N$. In this situation, the optimal algorithm for guessing the number is a simple Binary search algorithm, which finds $x$ in order $O(\log_2N)$. This formula intuitively says how many questions you need to ask to find out what's $x$. For example, if $N=8$, you need to ask maximum 3 questions to find the unkown $x$. 
From the probabilistic perspective, when you declare $x$ as being equally likely to be any values in range $1 \leq x \leq N$, it means $p(x) = 1/N$ for $1 \leq x \leq N$. Claude Shannon nicely showed that the information content of an outcome $x$ is defined as: 
\begin{equation}
h(x) = \log_2 \frac{1}{p(x)}
\end{equation}
The reason for the base 2 in the logarithm is that here we're measuring the information in bits. You can also assume natural logarithm which makes your information measure in nats. As an example, the information content of outcom $x=4$ is $h(4) = 3$. This value is precisely equal to the number of steps in the binary search algorithm (or number of IF statements in the algorithm). Therefore, the number of questions you need to find out $x$ is equal to $4$, is exactly the information content of the outcome $x=4$. 
We can also analyze the performance of the binary search algorithm for any possible outcome. One way of doing that is to find out what's the expected number of questions to be asked for any values of $x$. Note that the number of required questions for guessing a value of $x$, as I discussed above, is $h(x)$. Therefore, the expected number of questions for any $x$ is by definition equal to:
\begin{equation}
\langle h(x) \rangle  =   \sum_{1 \leq x \leq N} p(x) h(x)
\end{equation}
The expected number of questions $\langle h(x) \rangle$ is just same as the entropy of an ensemble $H(X)$, or entropy in short. Therefore, we can conclude that entropy $H(X)$ quantifies the expected (or average) number of the questions one need to ask in order to guess an outcome, which is the computational complexity of the binary search algorithm. 

