This is not an answer to the question (which I think is well-addressed by Micah's comment above) but a compendium of miscellaneous observations.
First, Micah's comment points out that it would be very surprising if there were not a solution for all sufficiently large $N$, and computer search bears this out: there are solutions for $N=1,15,16,17, 23,$ and all numbers between $25 $ and $50$, at which point I stopped checking. As $N$ increases, the number of solutions increases very rapidly; there is 1 solution for $N=15$, ten solutions for $N=25$, and $17,175$ for $N=35$. The $N=15$ case is atypically constrained.
Finding the solution when $N=15$ is very easy. One can begin by observing that $9$ is adjacent only to $7$, and $8$ only to $1$, so the solution, if it exists, must begin with $9$ and end with $8$. (Or vice-versa, giving the same solutions in reverse, which we henceforth disregard.) But the moves from $9$ are forced: $9-7-2-14-11-5-4-12-13-3$ is the only sequence possible. From $3$ one can go to $1$ or to $6$, and since going to $1$ evidently doesn't work (since we know $1$ is next-to-last) it must end $3-6-10-15-1-8$ and that is the only solution.
Consider the graph whose nodes are $\{1,\ldots, 15\}$ in which has two nodes are connected whenever their sum is a square. A solution to the problem is exactly a hamiltonian path in this graph. When we look at this graph, the uniqueness of the solution is completely obvious:
and even a child can see that there is only a single hamiltonian path. (I know because I checked with my six-year-old daughter, who agrees.) The graphs for $N=16$ and $N=17$ are similarly trivial, and a glance at the graph for $N=18$ or $N=19$ shows why there is no solution for those values:
In $N=20, 21, 22$ the lack of solutions is still easy to see, although the troublesome dead end at 16 has been connected to 5 via 20. For $N=24$ I did not see any obvious reason why there is no solution, but I think a simple argument could probably be made involving the disposition of $11, 22, $ and $23$.
I have not done much investigation of the analogous problem where two numbers are connected if their sum is a perfect cube. For $N=100$ the graph is not even connected. For $N=200$ it is connected, but has many leaves. Even for $N=300$ I suspect there is a fairly easy proof that there is no solution, involving the relatively independent cluster of $\{29, 35, 90, 126, 217, 253, 259\}$ which has only 4 connections to the rest of the graph.
Partial answer.
Theorem: Any group of order $n$ is cyclic $\Longleftrightarrow \gcd(n,\varphi(n))=1$
It follows that if there is a non-cyclic group of order $n$, then neither of $n^n+\varphi(n)$ and $\varphi(n)^{\varphi(n)}+n$ is a prime.
This means that $n$ needs to be a product of distinct primes none of which divides another lowered by $1$ (e.g. $15=3\times 5$ with $3\not\mid (5-1)$).
See OEIS A003277. Funny fact, although I don't see how that can really be relevant here, that for such numbers, $\varphi(n)^{\varphi(n)}\equiv 1\bmod n$.
Best Answer
This is mostly just a summary of what I have found that is to big for a comment.
Since $\varphi(\varphi(n))$ must be a power of $2$, $\varphi(n)=2^m p_1 p_2 p_3...p_m$. Where each of the $p_i$ is a distinct Fermat prime. Thus we have $$\varphi(n)^{\varphi(\varphi(n))}+1=(2^mp_1p_2p_3...p_m)^{2^r}+1.\tag{1}$$ We also have that $$n=2^uq_1q_2...q_sp_1^{e_1}p_2^{e_2}...p_m^{e_m}$$ where the $q_i$ are primes of the form $2^dp_i+1$, and the $e_i$ are each $0,1$ or $2$. If a $q_i$ is present in the factorization, then $e_i$ is at most $1$.
If we want to answer your question, it will probably be easiest to work with the right side of $(1)$.