What are some surprising appearances of $e$? I recently came across the following beautiful and seemingly out-of-the-blue appearance of $e$: 

$E[\xi]=e$, where $\xi$ is a random variable that is defined as follows. It's the minimum number of $n$ such that $\sum_{i=1}^n r_i>1$ and $r_i$ are random numbers from uniform distribution on $[0,1]$.

I can think of several more almost magical applications of $e$,$^\dagger$ but I would like to hear of some instances where you were surprised that $e$ was involved.
I would like to collect the best examples so as to be able to give some of the high-school students I tutor in math a sense of some of the deep connections between different areas of math that only really become apparent at the university level. These deep connections have always made me want to learn more about math, and my hope is that my students would feel the same way. 
EDIT (additional question): A lot of the answers below come from statistics and/or combinatorics. Why is $e$ so useful in these areas? In general, I'd very much appreciate if answerers included some pointers as to how one can get an intuition about why $e$ appears in their case (or indeed, how they themselves make sense of it) - this would greatly help me in presenting these great examples.

$^\dagger$For instance that its exponential function is its own derivative, its relation to the trigonometric functions, its use in Fourier transformation, transcendence, etc., all of which I must admit I don't really understand (perhaps except for the first one, which I take to be the definition of $e$), as in "what is it about $e$ that makes it perfect for representing complex numbers, or changing from one basis to another, etc.?"
 A: $e$ finds itself in formulas involving $\pi$. Ramanujan's constant $$e^{\pi \sqrt{163}} = 262537412640768743.99999999999925\ldots \approx 640320^3+744$$
is related to Heegner numbers and has deep connections to number theory. 
The Gaussian integral $$\int_{-\infty}^{+\infty} e^{-x^2}\,dx = \sqrt{\pi}$$ is related to polar coordinates and thus Euler's famous formula. 
A: Pick non-overlapping pairs $(x,x+1)$ of integers from $[1,n]$ until no more pairs can be picked (i.e., until no more consecutive integers remain), and let $p$ be the number of integers that were picked (i.e. $w$ is twice the number of picked intervals). Then you have for the expected value $\mathbb{E}\ p$ of picked integers that $$
  \lim_{n\to\infty} \frac{1}{n}\mathbb{E}\ p = 1-e^{-2}.
$$
This is a discrete version of Renyi's car parking constant, which is due to Page (1958), "The  distribution  of  vacancies  on  a  line", J. R. Statist. Soc. B 21, 364–374.
A: I don't know if this is relevant, but the fact that both $e$ and $\pi$ appear in the Gaussian function defining the normal distribution (which is very important in probability and in statistics) is something I find beautiful :
$$f(x) = \frac{1}{\sqrt{2π}}e^{-\frac{x^2}{2}}$$
Another example : $e$ appears in the definition of the moment-generating function $M_X(t)=E[e^{tX}]$ which is also very useful in probability and in statistics.

Here is an another interesting appearance of $e$:
$$y=[1,3,5,7,9,11,\cdots]=1+\dfrac{1}{3+\dfrac{1}{5+\dfrac{1}{7+\dfrac{1}{9+\cdots}}}}=\dfrac{e^2+1}{e^2-1}$$ 
This is a particular case of the Continued Fraction Expansion of $\tanh(\cdot)$, see (1) or (2).
Other continued fractions involving $e$ can be found here, for instance:
$$1+\dfrac{1}{1+\dfrac{1}{2+\dfrac{2}{3+\dfrac{3}{4+\cdots}}}}=e-1$$ 
A: The graph of $$y=x^x, x>0$$ has minimum value $$y=\left(\frac 1e\right)^{\frac 1e}$$ when $x=\frac 1e$
A: The arithmetic mean of the first $N$ positive integers is about $N/2$. This is easy to justify without any computation. Less obviously, the geometric mean of the first $N$ positive integers is about $N/e$.
A: Throw $N$ balls into $N$ bins at random. The probability that any given bin is empty is $e^{-1}$, and thus with high probability the fraction of empty bins is close to $e^{-1}$.
A: $e$ appears in the basic Stirling's approximation for the factorial.
$$n!\approx\left(\frac ne\right)^n$$ hence
$$e\approx\frac n{\sqrt[n]{n!}}.$$
A: What is the radius of convergence of the power series
$$
f(x)=\sum_{n=0}^\infty \frac{n! x^n}{n^n}?
$$
Answer. Exactly $\mathrm{e}$.
A: I would add to the list Dobiński's formula for the $n^{\rm th}$ Bell's number (the number of partitions of an $n$-element set) which is given by
$$B_n = {1 \over e}\sum_{k=0}^\infty \frac{k^n}{k!}.$$
When I first saw this formula I was amazed by an appearance of $e$ in a formula for a very concrete natural number. 
A: I have a silly one, which is mine and even if it's not really correct, it's quite cute!
Be: 
$\pi$ the famous constant we all know
$\phi$ the golden ratio
$\gamma$ = Euler-Mascheroni constant
Thence
$$e \approx \frac{\pi + \phi + \gamma}{\pi\phi\gamma -1}$$
Anyway, as I said it's not really correct because
$$\frac{\pi + \phi + \gamma}{\pi\phi\gamma -1} - e = 0.0410(...)$$
A: Take a conventional s-wave superconductor, then if we are looking into its bulk one might find (details):
$$
\frac{\Delta_0}{k_b T_c}=\pi e^{-\gamma}
$$ 
where $k_b$ is the Boltzmann constant, $\Delta_0$ is the gapsize at zero temperature and $T_c$ is the critical temperature.
Note that the r.h.s. of the formula above is independent of any material parameter but  instead given by this wonderful combination of mathematical constants. This was very surprising to me when i saw it the first time.
There is another very similar relation if we put our superconductor additionally into an magnetic field. This case can also be found in the reference above.
A: We have

$$e=\lim_{n\to\infty}\sqrt[\large^n]{\text{LCM}[1,2,3,\ldots,n]},$$

where LCM stands for least common multiple.
The proof can be found here.
A: $e$ appears in the number of derangements
The formula for the number of derangements of length $n$ turns out to be 
$$n! \cdot \sum_{j=0}^n \frac{(-1)^j}{j!}$$
Since the second part is just the standard series for $e^{-1}$ this can also be written as
$$\bigl[ \frac{n!}{e} \bigr]$$
where $[ . ]$ denotes the closest integer.
This also implies that the percentage of derangements among all permutations approaches, as $n \to \infty$ the number $\frac{1}{e}$.
A: You could look up some interesting topics such as Bernoulli trials, which use Euler's number to approximate probabilities involving large numbers, and Stirling's approximation which provides an approximation for factorials.
I always liked the inequality rule that e is the only real number for which the following is true:
$$\left(1+\frac{1}{x}\right)^x < e < \left(1+\frac{1}{x}\right)^{x+1}$$
A: Rather in the same area as the example you give in your question, but in this case an open problem rather than a theorem, is Feige's conjecture:
Let $X_1,...,X_n$ be independent non-negative random variables with unit expectation. Then $$\mathrm P[X_1+\cdots+X_n\leqslant n+1]\!\geqslant\frac1{\mathrm e}.$$
The non-negativity and unit expectation are obviously essential conditions, and independence is important too, but note that there are no other restrictions on the distributions of the random variables.
A: My favourite, also in the area of probability, is the secretary problem. Copied (with editing) from the Wikipedia site:
The task is to hire the best of $n$ applicants for a position. The applicants are interviewed one by one in random order. A decision about each one must be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the interviewer can rank the applicant among all those interviewed so far, but is unaware of the quality of yet unseen applicants.
If you interview all applicants, then you are obliged to pick the last one. Is there a better strategy?
The answer is yes: interview $n$/e of the candidates (to the nearest whole number) and then choose the first of the remaining candidates who is better than any of those interviewed before; if none of them are, up to candidate $n-1$, then you still have to choose candidate $n$.
A: I have two approximation of almost an integers involving e
$$10e^{\pi\phi\over 2}\approx 126.99998...$$
$$\left({6\over 5}\phi^2-\pi\right)^{-2^{-2}}-\left({10\over \pi}+10\right)^{-2}-e^{-\phi\pi{e}}\approx 11.99999989...$$
A: Here is another one that can be founded in the book Escapades Arithmétiques written by Frédéric Laroche :

$$1+\frac 1{1\cdot 3}+\frac 1{1\cdot 3\cdot 5}+\cdots+\frac 1{1+\frac 1{1+\frac 2{1+\frac 3{1+\cdots}}}}=\sqrt{\frac{e\pi}2}.$$

Perhaps in a more explicit way:
$$\sum_{k=0}^\infty \left(\prod_{j=0}^k (2j+1)\right)^{-1}=\sqrt{\frac{e\pi}2}.$$
A: Euler's integral formula (Gamma function) impressed me a lot:
$$n!=\int_{0}^{\infty}e^{-x}x^ndx$$
where natural exponential of the negative and $n$-th power mix up in a simple and complicated way to give the $n$ factorial (generalized).
A: I think the appearance of the exponential function (so not exactly $e$) in linear differential equations is pretty amazing. We are very much used to it because we use it so often, but it is interesting that all linear first order dynamics are depending on the exponential function.
If we have $$\sum_{n=0}^{N}a_ny^{(n)}(x)=0$$
then the solution is given by
$$y(x)=\sum_{m=1}^{M}p_m(x)e^{\lambda_m x}$$
In which $p_m(x)$ is a polynomial of degree $a_m$ which is the multiplicity of the eigenvalue $\lambda_m$. 
Sure we could choose another base but the natural base is $e$.
A: An almost magical appearance of $e$ comes from Pascal's Triangle. Let $s_n$ be the product of the terms on the $n$-th row of the Pascal's Triangle, that is:
$$s_n=\prod_{k=0}^n\binom{n}{k}$$
Then
$$\lim_{n\to \infty}\frac{s_{n-1}s_{n+1}}{s_n^2}=e$$
A proof of this fact can be found here. I think it's one of the things that struck me the most about Pascal's Triangle, and nowadays, it stills surprises me.
A: Here's a nice (longish) one. 
A sequence of numbers $x_1,x_2,...$ is generated randomly from $[0,1]$. This process is continued so long as the sequence is monotonically increasing or monotonically decreasing. 
Q: What is the the expected length of the monotonic sequence?
The probability that the length $L$ of the monotonic sequence is greater than $k$ is given by $$P(L>k) = P(x_1<x_2<\cdots<x_{k+1})+P(x_1>x_2>\cdots>x_{k+1})$$
$$ = \frac{1}{(k+1)!} + \frac{1}{(k+1)!}$$
$$ = \frac{2}{(k+1)!}$$
If we now call $P(L=k)$ by $p_k$, the expected length of the monotonic sequence is $$E(L) = 2p_2+3p_3+\cdots+np_n+\cdots$$
We can write this as,
$$E(L) = 1+1+P(L>2)+P(L>3)+P(L>4)\cdots$$
$$ = 1+1+2\bigg(\frac{1}{3!}+\frac{1}{4!} +\frac{1}{5!} +\frac{1}{6!}+\cdots\bigg)$$
$$=1+1+2\bigg(e-\frac{5}{2}\bigg)$$
$$= 2e-3$$
Tada!
A: I kind of think this is cheating, but Euler's Identity comes to mind:

$$e^{i\pi}+1=0$$

This is a specific case of $e^{ix}=\cos x+i\sin x$ when $x=\pi$. Deriving the formula requires only a knowledge of the Taylor expansions of $e^x$, $\sin x$, and $\cos x$.
I suppose this is not particularly surprising, but it reveals a very deep connection between the trigonometric functions, exponential functions, and even basic arithmetic.
EDIT: I wanted to add this as an afterthought:
In $e^{ix}=\cos x+i\sin x$ let $x=\frac{\pi}{2}$.
$\displaystyle e^{i\frac{\pi}{2}}=0+i$. Now exponentiate both sides by $i$.
$\displaystyle (e^{i\frac{\pi}{2}})^i=i^i \Longrightarrow e^{-{\frac{\pi}{2}}}=i^i$ 
$i^i$ is a real number, expressible in terms of $e$.
A: In section 1.3 of Mathematical Constants by S.R. Finch we find this  connection to prime number theory
\begin{align*}
\lim_{n\rightarrow \infty}\left(\prod_{{p\leq n}\atop{p \text{ prime}}}p\right)^{\frac{1}{n}}=e
\end{align*}
and also some Wallis-like infinite products
\begin{align*}
e&=\frac{2}{1}\cdot\left(\frac{4}{3}\right)^{\frac{1}{2}}\cdot
\left(\frac{6\cdot 8}{5\cdot 7}\right)^{\frac{1}{4}}\cdot
\left(\frac{10\cdot12\cdot14\cdot16}{9\cdot11\cdot13\cdot15}\right)^{\frac{1}{8}}\cdots,\\
\ \ \frac{e}{2}&=\left(\frac{2}{1}\right)^{\frac{1}{2}}\cdot\left(\frac{2\cdot4}{3\cdot3}\right)^{\frac{1}{4}}
\cdot\left(\frac{4\cdot6\cdot6\cdot8}{5\cdot5\cdot7\cdot7}\right)^{\frac{1}{8}}\cdots
\end{align*}
A: Probably and happily, this is an important one 
$$e^{tA}=1\!\!1+tA+\frac{1}{2!}t^2A^2+\cdots$$
for a squared matrix $A$ and each parameter $t$. 
A: The minimum value of the function $f(x) = x^x$ is $f \left( \frac{1}{e} \right) = \left( \frac{1}{e} \right)^{\frac{1}{e}} \approx f(0.368) \approx 0.692$.
