I recently came across the following question (paraphrasing):
Find the largest integer $n$ such that, for some polynomial $f \in \mathbb{F}_{13}[x]$, the $n$-fold iterate of $f$, but no lesser iterate, is the identity map on $\mathbb{F}_{13}$.
There are immediate lower bounds of $13$, from $f(x) = x + 1$, and an upper bound of $60$, because the maximum order of an element of $S_{13}$ is $g(13) = 60$ ($g$ is Landau's function), given by permutations with cycle lengths $\{5, 4, 3, 1\}$. In general, if $R$ is a finite ring and $f \in R[x]$ permutes $R$, then call the order of the induced permutation the order of $f$, and say that $f$ has maximal order over $R$ if its order is $g(|R|)$.
With trial and error following Wikipedia's list of permutation polynomials, I managed to find polynomials of maximal order not only over $\mathbb{F}_{13}$ but over all $\mathbb{F}_p$ for $p \leq 13$ prime:
$$\begin{array}{cccc} \text{field} & \text{polynomial} & \text{permutation} & \text{order} \\ \hline \mathbb{F}_2 & x + 1 & (0~1) & 2 \\ \mathbb{F}_3 & x + 1 & (0~1~2) & 3\\ \mathbb{F}_5 & x^3 + 2 & (0~2)(1~3~4) & 6 \\ \mathbb{F}_7 & x^5 + 2x^2 + 3 & (0~3~5)(1~6~4~2) & 12 \\ \mathbb{F}_{11} & 2x^3 + 2 & (0~2~7~6~5~10)(1~4~9~8~3) & 30\\ \mathbb{F}_{13} & x^5 + 2x^3 + 12x + 6 & (0~6~5~9~2)(1~8~3)(4~10~11~12)(7) & 60 \end{array}$$
I can't find any obvious pattern in the polynomials I've found and I'd like to know whether this generalizes, ideally with a constructive proof:
Does every finite field of prime order $\mathbb{F}_p$ with $p$ prime have a polynomial in $\mathbb{F}_p[x]$ that induces a permutation on $\mathbb{F}_p$ with maximal order $g(p)$?
Can the same be said about other classes of finite rings, such as the fields of composite order $\mathbb{F}_{p^k}$ or the rings $\mathbb{Z}_n := \mathbb{Z}/n\mathbb{Z}$ for composite $n$?
Regarding the second question, I have found that $x + 1$ has maximal order over $\mathbb{Z}_4$ and $\mathbb{Z}_6$, and $ax + 1$ (where $a$ is either element of $\mathbb{F}_4$ that satisfies $a^2 + a + 1 = 0$) has maximal order over $\mathbb{F}_4$. These examples give cyclic permutations, though, and are thus trivial. My unsystematic experiments with $\mathbb{Z}_8$, $\mathbb{Z}_9$, and $\mathbb{Z}_{10}$, looking for permutations with respective cycle lengths $\{5, 3\}$, $\{5, 4\}$, and $\{5, 3, 2\}$, have not succeeded. There seems to be a strong tendency for polynomial permutations of composite-order rings $\mathbb{Z}_n$ to have distinct cycle lengths not relatively prime to $n$. (For example, permutation polynomials on $\mathbb{Z}_9$ commonly give cycles of length $\{3, 3, 3\}$ or less often $\{3, 2, 2, 2\}$; a frequent cycle structure on $\mathbb{Z}_{10}$ is $\{4, 4, 2\}$.)
Any function $f: \mathbb{F}_p \to \mathbb{F}_p$ can be realized by a polynomial (in infinitely many ways), this can be seen by say using Lagrange interpolation. So indeed the maximal orders of permutations are always attainable in many different ways.
The same holds over $\mathbb{F}_q$, I'm not sure about $\mathbb{Z}/p^k\mathbb{Z}$ though off the top of my head.
I'll note though that Lagrange interpolation would give you polynomials of degree roughly p, and you seem to be finding ones of significantly lower degree. Proving this with a better degree bound seems interesting.