Let $a_1 < a_2 < \dots < a_n$ be the elements of $A$. The diameter of $A$ is $d(A) = a_n - a_1$. The minimum and maximum of $A + A = \{x + y \mid x, y \in A\}$ are $a_1 + a_1$ and $a_n + a_n$. Since $A + A$ has $\frac{n(n+1)}{2}$ elements, $2a_n - 2a_1 + 1 \ge \frac{n(n+1)}{2} \iff d(A) \ge \frac{n^2}{4} + \frac{n-2}{4} \ge \frac{n^2}{4}$.

To prove the upper bound, we need to construct a set $A$ with property $P$ such that $d(A) < n^3$. We do this recursively. Start with $A = \{0, 1\}$ and we will adjoin elements to $A$. Suppose we already have $a_1 = 0 < a_2 = 1 < \dots < a_n$ in $A$ such that $\{a_1, a_2, \dots, a_n\}$ has property $P$. Adjoining $a_{n+1}$ will generate $n+1$ more sums: $a_1 + a_{n+1}, a_2 + a_{n+1}, \dots, a_{n+1} + a_{n+1}$. All these sums must be different from any $a_i + a_j$, $1 \le i \le j \le n$. Moreover, $a_{n+1}$ must be different from all numbers $a_i$, $1 \le i \le n$. This means that $a_{n+1} \notin \{a_i + a_j - a_k \mid 1 \le i \le j \le k\} \cup \left\{\frac{a_i+a_j}{2} \mid 1 \le i,j \le n\right\} = B$. This set has no more than $n^3 + \frac{n(n+1)}{2}$ elements. So we may choose $a_{n+1}$ as the smaller number not in $B$, and so $a_{n+1} \le n^3 + \frac{n(n+1)}{2} < (n+1)^3$. Thus
$d(A) = a_{n+1} - a_1 = a_{n+1} < (n+1)^3$.

Now we are going to prove the “bonus” part of the problem. Let $p$ be a prime and consider $A = \{k + 2p \cdot (k^2 \bmod p) \mid 0 \le k \le p-1\}$. We have
$d(A) \le (p-1)+2p(p-1) = 2p^2-p-1 < 2p^2$. Moreover, $r+2p(r^2 \bmod p)+$
$s+2p(s^2 \bmod p) = t+2p(t^2 \bmod p)+u+2p(u^2 \bmod p) \iff r+s=t+u$
and $r^2 \bmod p + s^2 \bmod p = t^2 \bmod p + u^2 \bmod p$. So $r-t=u-s$ and
$r^2-t^2 \equiv u^2-s^2 \pmod p \iff (r-t)(r+t) \equiv (u-s)(u+s) \pmod p$
$\iff r-t \equiv u-s \equiv 0 \pmod p$ or $r+t \equiv u+s \pmod p$, hence
$r=t$ and $s=u$ or $r=u$ and $s=t$.