What is the fastest growing total computable function you can describe in a few lines?
Most fast-growing functions are constructed by a recursive scheme analogous to the well-known Ackermann function - namely one repeatedly iterates a function and then diagonalizes. Thus iterating addition yields multiplication, which iterated yields exponentiation, which iterated yields tetration, etc. Diagonalizing the resulting sequence of functions yields a faster-growing Ackermann function - which itself may be successively iterated, diagonalized, etc. Paul du Bois-Reymond discovered such diagonalization on growth rates of functions ("orders of infinity") in 1875, long before Cantor's better-known rediscovery (1891), employed to show $|2^S| > |S|$.
Proof-theorists use analogous recursive schemes to construct notation systems for ordinals - which they employ to measure the strength of logical systems. Functions and numbers notated by such means (whether finite or infinite) tremendously dwarf those that occur in most all other branches of mathematics. Thus I highly recommend that you consult the literature on ordinal notation systems.
Below are some expository references on related topics (from an old sci.math post).
[Ruc] Rucker, Rudy. Infinity and The Mind, 1995, 342 pp. Princeton U. Pr.
[Spe] Spencer, Joel. Large numbers and unprovable theorems, Amer. Math. Monthly, Dec 1983, 669-675.
[Smo] Smorynski, Craig (all three papers are reprinted in [HFR])
Some rapidly growing functions, Math. Intelligencer, 2 1980, 149-154.
The Varieties of Arboreal Experience, Math. Intelligencer, 4 1982, 182-188.
"Big" News from Archimedes to Friedman, Notices Amer. Math. Soc. 30 1983, 251-256.
[Kol] Kolata, Gina. Does Godel's theorem matter to mathematics? Science 218 11/19/1982, 779-780; reprinted in [HFR]
[Sim] Simpson, Stephen G. Unprovable theorems and fast-growing functions, Contemp. Math. 65 1987, 359-394.
[HFR] Harrington, L.A. et.al. (editors) Harvey Friedman's Research on the Foundations of Mathematics, Elsevier 1985.
For a nice fast-growing function, consider the following:
Given rooted trees $S$ and $T$ whose vertices are labeled from $\{1,2,\cdots,k\}$, define a gap embedding as a label preserving embedding $h$ from $S$ into $T$ that satisfies the following: given $u$, $v$ vertices of $S$ such that $v$ is the child of $u$. For any vertex $w$ of $T$ that lies in between $h(u)$ and $h(v)$, $l(w) \ge l(h(v))$.
Given this definition, define $ETree(k)$ to be the longest sequence $T_i$ of rooted trees labeled from $\{1,2,\cdots,k\}$ such that $T_i$ has no more than $i$ vertices, and for no $i < j$ is there a gap embedding from $T_i$ into $T_j$.
The above construction is due to Harvey Friedman. He showed that no such sequence could be infinite (i.e. that rooted labeled trees are well-quasi-ordered under gap embedding), and it follows from Koenig's Tree Lemma that there is a longest such sequence.
The function $ETree(k)$ grows extremely fast. It grows at the rate of $F_{\psi_{\Omega_1} (\Omega_\omega)} (k)$. (Look up the fast-growing hierarchy.)
One can also get extremely fast growing functions using ordinal hierarchies. Let $I(a)$ be the $a$'th weakly inacessible cardinal. Consider the following: (here $a,b,c,d,e$ are ordinals, $\phi$ is the Veblen function, $C_n(a,b)$ are sets of ordinals, $\psi$ and $f$ are functions on ordinals.)
$C_0(a,b) = b \cup {0}$
$C_{n+1}(a,b) = \{c+d, \phi(c,d), \aleph_c, I(c), \psi(e,d), f(e,c,d) | c,d,e \in C_n(a,b), e < a\}$
$C(a,b) = \cup C_n(a,b)$
$f(a,n,b) =$ largest finite ordinal in $C_n(a,b)$
$\psi(a,b) = b$'th ordinal such that $b \notin C(a,b)$
Then, for example, $f(I(I(I(I(0)))),x,x)$ is an extremely fast growing function, much faster than $ETree$. To help understand this construction, see "Ordinal collapsing function" on wikipedia. If that is still confusing, look at
http://math.ucr.edu/home/baez/week236.html
for an introduction to ordinals, and
http://groups.google.com/group/sci.math/browse_thread/thread/b4b2769c6359b3e9/5317b10cbf60196
for a description of how ordinals can be used to define large numbers.
EDIT: Perhaps some more explanation is needed. $C(a,b)$ is the smallest set of ordinals containing all ordinals less than $b$ and $0$ and closed under the operations listed in the second line. The definition may appear circular, but it is well-defined by induction on $a$; given $f(c,n,b)$ and $\psi(c,b)$ for $c < a$, we define $C_n(a,b)$, and given $C_n(a,b)$, we define $f(a,n,b)$ and $\psi(a,b)$.
Some analysis of $f(a,n,b)$:
$f(0,0,b)$ is the largest finite ordinal in $C_0(0,b) = b$, which is $b-1$.
$f(0,1,b)$ is $2(b-1)$ if $b \ge 2$, otherwise it is $\phi(0,0) = 1$.
$f(0,n,b)$ is $2^{b-1}$ if $b \ge 2$, otherwise it is $2^{n-1}$
$f(1,0,b)$ is again $b-1$ if $b \ge 1$, $0$ if $b = 0$
$f(1,1,b)$ is $2^{b-1} (b-1)$ if $b \ge 2$ otherwise it is $1$
$f(1,n,b) > Tower_n (b-1) > 2\uparrow\uparrow n$ for $b \ge 2$
$f(2,n,b) > 2\uparrow\uparrow\uparrow n$ for $b \ge 2$
$f(m,n,b) > 2 \uparrow^{m+1} n$ for $b \ge 2$
$f(\omega,0,b) = b-1$ for $b \ge 2$
$f(\omega,1,b) = f(b-1,b-1,b-1) \ge 2 \uparrow^{b}(b-1)$ for $b \ge 2$
$f(\omega,2,b) = f(f(\omega,1,b),f(\omega,1,b),f(\omega,1,b)) \ge 2 \uparrow^{2 \uparrow^b (b-1)}(2 \uparrow^b (b-1))$
$f(\omega,n,b)$ is the function $f(x,x,x)$ applied $n$ times starting from $b-1$, which is greater than $F_{\omega+1}(n)$ where $F$ is the fast-growing hierarchy.
$F(\omega+1,n,b)$ is the function $f(\omega,x,x)$ applied $n$ times starting from $b-1$, which is greater than $F_{\omega+2}(n)$.
Each time we add $1$ to $a$, we go to a function which iterates the previous one $n$ times; each time we increase a to a limit ordinal, we diagonalize over previous functions. So the task becomes defining very large countable ordinals.
I do not know whether it is the fastest, but historically the Ackermann function was the first (afaik):
$\qquad A(m, n) =\begin{cases}n+1 & \mbox{if } m = 0 \\A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.\end{cases}$
It generalises the idea that $+$, $\cdot$, $\exp$ and so on form a natural series of operators; $A$ excedes them all by controlling the stacking level in the second parameter.
It has been proven that $A$ (or rather $A(n,n)$) is not primitive recursive by showing that it grows faster than any primitive recursive function, including all exponential functions.