Dear Nate, first, why is $e$ the preferred base for exponentials? Imagine that you have 1 dollar and your bank gives you 100% interest rate. After 1 year, you will have 2 dollars.
Now it offers you to add interests 100 times in a year but the interest is 1% at each moment. How much will you get? You will get
$$ (1+0.01)^{100} \approx 2.704 $$
What if they add you $1/N \times $ 100% at $N$ moments of the year and you send $N$ to infinity? Well, you will have $e\approx 2.71828$ dollars after one year.
In fact, the general exponential - power with the base of $e$ - may be defined by this "repeated small interest" formula as
$$ e^X = \exp(X) = \lim_{N\to \infty} \left(1+\frac {X}{N}\right)^N $$
It only has this simple form if the base is $e$. A more general power may be defined as
$$ Y^X = \exp(X \ln Y) .$$
Here, $\ln$ is the natural logarithm so that $\exp\ln X = X$. If I replaced the base $e$ by another base such as $2$ or $10$, the "repeated small interest" formula above would have to contain $\ln 2$ or $\ln 10$ or other awkward factors at various places. It wouldn't be natural.
So instead of powers $Y^X$ and logarithms with general bases, you should think that in mathematics, only $\exp(X)$ and $\ln(X)$ are really needed, and all the other powers and logarithms may be expressed as composite functions. Also, $\exp(X)$ has the advantage that its derivative is exactly equal to the very same function $\exp(X)$. In particular, the derivative evaluated at $X=0$ is equal to one, very nice and simple. It would be $\ln(Y)$ if you used a different base $Y$ instead of $e$.
Now, what is the exponential of an imaginary exponent? Again, you may write
$$\exp(iX) = \lim_{N\to\infty} \left(1+\frac {iX}{N}\right)^N $$
You multiply $N$ copies of a number that is very close to one. What do you get?
Well, the multiplication by a complex number has the effect of magnifying (or reducing) the plane, and rotating it. In particular, the absolute value of the number $(1+iX/N)$ is essentially one, up to second-order corrections that disappear in the $N\to \infty$ limit. So in the limit, $(1+iX/N)$ is effectively a number whose absolute value equals one.
Multiplying by complex numbers whose absolute value is equal to one looks like a rotation of the complex plane. The angles are preserved - those are some things one should know about the complex numbers. Moreover, it's clear that multiplying by $(1+iX/N)$ is equivalent to the rotation by $X/N$ in radians. If you multiply the same factor $N$ times, you simply get a rotation by $X/N$ in radians.
So the $N$th power of $1+iX/N$, in the limit $N\to\infty$, is the number that you get by rotating $1$ in the counter-clockwise direction by the angle $X$ in radians. Clearly, the answer is
$$ \exp(iX) = \cos (X) + i \sin(X) $$
where the trigonometric functions have arguments in radians, of course. Once again, the mathematically natural unit of an angle is in radians for very similar reasons why the natural base of the powers or exponentials is $e$. Only in radians, it's true that the derivative of $\sin X$ equals $\cos X$ and many other things.
In fact, the previous formula makes it natural to say that $\cos X$ and $\sin X$ are not "independent" functions, either. They may be defined as
$$\cos (X) = \frac 12 ( e^{iX} + e^{-iX} ) $$
$$\sin(X) = \frac{1}{2i} (e^{iX} - e^{-iX} ) $$
You may substitute the last two equations into the previous one or vice versa to check that everything is consistent.
Just to be sure, general complex numbers may also be exponentiated via $\exp(A+iB) = \exp(A)\exp(iB)$ where both factors are known.
Let's count how many modular multiplications we need to do to get to $x^{25}$ with the two methods. The trivial method would need 24 multiplications (I leave out the calculation of the residue modulo $N$ - that will always be there): $x^2=x*x$, $x^3=x^2*x$, $x^4=x^3*x$, $\ldots$, $x^{25}=x^{24}*x$. With repeated squaring there are several approaches. We might first compute $x^2=x*x$, $x^4=(x^2)*(x^2)$, $x^8=(x^4)*(x^4)$, $x^{16}=(x^8)*(x^8)$. That is 4 multiplications so far. The point of doing this to store these values somewhere. Then we can compute $x^{24}=(x^{16})*(x^8)$ and $x^{25}=(x^{24})*x$ with just two extra multiplications. A total of 6 multiplications in comparison to 24. In the worst case we need to do about $2*\log_2m$ multiplications to compute $x^m$.
If you don't have enough memory to store that look table of powers $x^{2^k},k=0,1,\ldots,[\log_2m]$, then you can get away with less by using the approach outlined in Bill Dubuque's answer. In addition to $x$ itself you only need to store one other intermediate value. Here $25=11001_2$, and for a hopefully obvious reason I will also write the exponents in binary in parentheses in what follows. First compute the square
$$
x^2=(x^{10_2})=x*x.
$$
We notice that our exponent $25=11001_2$ begin with two 1s, so next we multiply this result
with $x$ and calculate
$$
x^3=(x^{11_2})=(x^2)*x.
$$
Notice that this calculation needed only the result of the previous multiplication and the input $x$. Let's square this
$$
x^6=(x^{110_2})=(x^3)*(x^3).
$$
Again we only needed the previous output $x^3$. Now we have the three leading bits from the exponent correctly in place, or because the third bit (starting with the most significant) of the exponent was 0, there is no need to multiply this by $x$. So we square again and get
$$
x^{12}=(x^{1100_2})=(x^6)*(x^6).
$$
Again we only needed the previous result ($x^6$). The fourth bit of the exponent was also a zero, so we can proceed with the final squaring
$$
x^{24}=(x^{11000_2})=(x^{12})*(x^{12}).
$$
The "previous value only" -comment applies again. The final bit of the exponent was a '1', so we need to fix it. The last multiplication is
$$
x^{25}=(x^{11001_2})=(x^{24})*x.
$$
To summarize: We square repeatedly. If the next bit of the exponent is a '1' we insert an extra multiplication with the original input.
Best Answer
My chief understanding of the exponential and the logarithm come from Spivak's wonderful book Calculus. He devotes a chapter to the definitions of both.
Think of exponentiation as some abstract operation $f_a$ ($a$ is just some index, but you'll see why it's there) that takes a natural number $n$ and spits out a new number $f_a(n)$. You should think of $f_a(n) = a^n$.
To match our usual notion of exponentiation, we want it to satisfy a few rules, most importantly $f_a(n+m) = f_a(n)f_a(m)$. Like how $a^{n+m} = a^na^m$.
Now, we can extend this operation to the negative integers using this rule: take $f_a(-n)$ to be $1/f_a(n)$. then $f_a(0) = f_a(n-n) = f_a(n)f_a(-n) = 1$, like how $a^0=1$.
Then we can extend the operation to the rational numbers, by taking $f_a(n/m) = \sqrt[m]{f_a(n)}$. Like how $a^{n/m} = \sqrt[m]{a^n}$.
Now, from here we can look to extend $f_a$ to the real numbers. This takes more work than what's happened up to now. The idea is that we want $f_a$ to satisfy the basic property of exponentiation: $f_a(x+y)=f_a(x)f_a(y)$. This way we know it agrees with usual exponentiation for natural numbers, integers, and rational numbers. But there are a million ways to extend $f_a$ while preserving this property, so how do we choose?
Answer: Require $f_a$ to be continuous.
This way, we also have a way to evaluate $f_a(x)$ for any real number $x$: take a sequence of rational numbers $x_n$ converging to $x$, then $f_a(x)$ is $\lim_{n\to\infty} f_a(x_n)$. This seems like a pretty reasonable property to require!
Now, actually constructing a function that does this is hard. It turns out it's easier to define its inverse function, the logarithm $\log(z)$, which is the area under the curve $y=1/x$ from $1$ to $z$ for $0<z<\infty$. Once you've defined the logarithm, you can define its inverse $\exp(z) = e^z$. You can then prove that it has all the properties of the exponential that we wanted, namely continuity and $\exp(x+y)=\exp(x)\exp(y)$. From here you can change the base of the exponential: $a^x = (e^{\log a})^x = e^{x\log a}$.
To conclude: the real exponential function $\exp$ is defined (in fact uniquely) to be a continuous function $\mathbb{R}\to\mathbb{R}$ satisfying the identity $\exp(x+y)=\exp(x)\exp(y)$ for all real $x$ and $y$. One way to interpret it for real numbers is as a limit of exponentiating by rational approximations. Its inverse, the logarithm, can similarly be justified.
Finally, de Moivre's formula $e^{ix} = \cos(x)+i\sin(x)$ is what happens when you take the Taylor series expansion of $e^x$ and formally use it as its definition in the complex plane. This is more removed from intuition; it's really a bit of formal mathematical symbol-pushing.