What's the explanation for why n^2+1 is never divisible by 3? What's the explanation for why $n^2+1$ is never divisible by $3$?
There are proofs on this site, but they are either wrong or overcomplicated.
It can be proved very easily by imagining 3 consecutive numbers, $n-1$, $n$, and $n+1$. We know that exactly one of these numbers must be divisible by 3. 
$$(n-1)(n)(n+1)=(n)(n-1)(n+1)=(n)(n^2-1)$$
Since one of those first numbers had to have been divisible by $3$, this new product $(n)(n^2-1)$ must also be divisible by $3$. That means that either $n$ (and by extension $n^2$) or $n^2-1$ is divisible by $3$. If one of those has to be divisible by $3$, then $n^2+1$ cannot be. 
So it is definitely true. My question is why is this true, what is inherent about $1$ more than a square number that makes it not divisible by $3$? Another way of saying this might be to explain it to me as if I don't know algebra.

Let $p$ be an odd prime.  Then, if there exists an integer $n$ such that $n^2+1$ is divisible by $p$, it must be that $p-1$ is divisible by $4$.
This requires using Fermat's Little Theorem, which says that $n^p-n$ is always divisible by $p$ (this can be shown using induction and divisibility arguments on binomial coefficients).  So, since $n$ cannot be divisible by $p$, $n^{p-1}-1$ is divisible by $p$.
We also need the fact that the set $S=\{k\in\mathbb{N} \mid n^k-1\text{ is divisible by $p$}\}$ must consist of multiples of a single number.  You can approach this using group theory, or prove that $\operatorname{gcd}(n^a-1,n^b-1)=n^{\operatorname{gcd}(a,b)}-1$ using the identity $(n^a-1)-(n^b-1)=n^b(n^{a-b}-1)$ for $a>b$.
But we also know that $n^4-1=(n^2+1)(n^2-1)$ is divisible by $p$, and $n^2-1$ is not divisible by $p$ (here is where we use that $p$ is odd).  So $S$ consists of exactly the multiples of $4$.  Since $p-1\in S$, $p-1$ is a multiple of $4$.
It turns out that the converse is also true: if $p-1$ is divisible by $4$, then there exists an integer $n$ such that $n^2+1$ is divisible by $p$.  This is a slightly more advanced fact, but it follows from the existence of primitive roots modulo a prime.  If $\zeta$ is a primitive root, then $n=\zeta^{\frac{p-1}{4}}$ is a solution.
Of course, I am assuming that you know some algebra... but this is what is "inherent" about the congruence $n^2\equiv -1$.  In the theory of groups, the above proof becomes a single line: "A cyclic group of order $p-1$ has an element of order $4$ if and only if $4$ divides $p-1$."
