It seems that for every prime $p$, $x^{p^2+p+1}-1$ and $(x+1)^{p^2+p+1}-1$ are not coprime in $\mathbb{F}_p$. In other words, it seems that there is always a $(p-1)$-th power $x$ in $\mathbb{F}_{p^3}^\times$ such that $x+1$ is also a $(p-1)$-th power in $\mathbb{F}_{p^3}^\times$.
Using PARI, one can calculate the degree of $\gcd(x^{p^2+p+1}-1, (x+1)^{p^2+p+1}-1)$ in $\mathbb{F}_p$ as follows: \begin{array}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline p & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 & 97 \\ \hline d & 6 & 6 & 6 & 7 & 12 & 18 & 12 & 18 & 24 & 36 & 36 & 36 & 36 & 36 & 60 & 48 & 66 & 54 & 72 & 72 & 72 & 72 & 90 & 96 & 108 \\ \hline \end{array} We can see that the degree listed here are very close to $p$. Also, $p=7$ is the only case where $\gcd(x^{p^2+p+1}-1, (x+1)^{p^2+p+1}-1)$ has a linear factor. If we remove that factor, then every degree here is divisible by $6$.
If we replace $p^2+p+1$ by $p^4+p^3+p^2+p+1$, we observe a similar pattern: the degree for $p=2,3,5,7,11,13,17$ is respectively $30,60,200,460,1642,2560,5590$. This seems to have a cubic growth with $p$, and after removing the linear factors for $p=11$, every degree seems to be divisible by $10$.
We have $$ (x+1)^{p^2+p+1} = x^{p^2+p+1} + x^{p^2+p} + x^{p^2+1} + x^{p^2} + x^{p+1} + x^p + x + 1, $$ but this does not seem to simplify $\gcd(x^{p^2+p+1}-1, (x+1)^{p^2+p+1}-1)$, so I think there must be a deeper reason for $\gcd(x^{p^2+p+1}-1, (x+1)^{p^2+p+1}-1)\neq 1$. Any idea appreciated.
I would like also to add that, since $3|(p^2+p+1)$ for $p\equiv 1\pmod 6$, I have also tested $\gcd(x^{\frac{p^2+p+1}{3}}-1, (x+1)^{\frac{p^2+p+1}{3}}-1)$ in $\mathbb{F}_p[x]$, which seems to be nonconstant other than $p=7,13,37,43,79$.
As Jyrki Lahtonen notes in the comments, the gcd is the product of all monic irreducible cubic polynomials $f(x)$ in $\Bbb{F}_p[x]$ such that $f(0) = f(-1) = -1$. So we're asking for the existence of an irreducible cubic of the form $f(x) = x^3 + ax^2 +(a-1)x - 1$.
Since this is a cubic polynomial, it is irreducible if and only if it has a root in $\Bbb{F}_p$. Note also that neither $0$ nor $-1$ is a root of $f(x)$ since $f(0) = f(-1) = -1$.
If $x$ is a root, we have $x^3-x-1 + a(x^2 + x) = 0$, so
$$a = \frac{x^3 -x - 1}{-x^2 - x}.$$
But then since $x \ne 0$ and $x \ne -1$, there are at most $p-2$ values of $a$ that satisfy the above equation for some $x \in \Bbb{F}_p$. So for at least $2$ values of $a$, $f(x)$ does not not have a root in $\Bbb{F}_p$ and is therefore irreducible.
So the degree of the gcd is at least $6$.