Elementary proof that $\mathbb{R}^n$ is not homeomorphic to $\mathbb{R}^m$
There are reasonably accessible proofs that are purely general topology. First one needs to show Brouwer's fixed point theorem (which has an elementary proof, using barycentric subdivion and Sperner's lemma), or some result of similar hardness. Then one defines a topological dimension function (there are 3 that all coincide for separable metric spaces, dim (covering dimension), ind (small inductive dimension), Ind (large inductive dimension)), say we use dim, and then we show (using Brouwer) that $\dim(\mathbb{R}^n) = n$ for all $n$. As homeomorphic spaces have the same dimension (which is quite clear from the definition), this gives the result. This is in essence the approach Brouwer himself took, but he used a now obsolete dimension function called Dimensionsgrad in his paper, which does coincide with dim etc. for locally compact, locally connected separable metric spaces. Lebesgue proposed the covering dimension, but had a false proof for $\dim(\mathbb{R}^n) = n$, which Brouwer corrected.
One can find such proofs in Engelking (general topology), Nagata (dimension theory), or nicely condensed in van Mill's books on infinite dimensional topology. These proofs do not use homology, homotopy etc., although one could say that the Brouwer proof of his fixed point theorem (via barycentric division etc.) was a precursor to such ideas.
is there intuition for why a proof is so difficult?
Sure: the topological category is horrible. A generic continuous function is bizarre and will violate your geometric intuitions. When we prove that $\mathbb{R}^n$ is not homeomorphic to $\mathbb{R}^m$ by proving that $S^n$ is not homotopy equivalent to $S^m$, much of the work goes into proving that, up to homotopy, we can ignore how bizarre generic continuous functions are. That is, you think that "homeomorphic" is an intuitive condition, but it's not.
This is why the corresponding question in the smooth category is much easier; generic smooth functions are much less bizarre in a way that is quantified by Sard's lemma.
Here is a specific example of what I mean. The reason we can distinguish $\mathbb{R}$ from $\mathbb{R}^m, m > 1$ by removing a point is because continuous functions send points to points. It is tempting to argue as follows: we can distinguish $\mathbb{R}^2$ from $\mathbb{R}^m, m > 2$ by removing a line, since the result is not connected for $\mathbb{R}^2$ but is connected for $\mathbb{R}^m$. But of course this argument doesn't work because continuous functions need not send lines to lines; the image of a line can be much bigger, e.g. all of $\mathbb{R}^m$.
This is weird. For $\mathbb{R}^2$, as you say, we can rescue this proof by removing a point because we know about simple connectedness and because, again, continuous functions send points to points. But for $\mathbb{R}^3$ we are stuck: removing a plane doesn't work, and removing a line doesn't even work, so if we want to stick to our "removing a point" strategy we had better figure out what the analogue of simple connectedness is in higher dimensions. This naturally leads to homotopy and homology, which happen to be strong enough tools to deal with the fact that continuous functions are bizarre, but they don't change the fact that continuous functions are bizarre.
Well, I might recast your proofs of the first two cases as follows:
Suppose that $\mathbb{R}^n$ and $\mathbb{R}^m$ are homeomorphic. Then for any $P \in \mathbb{R}^n$, there must exist a point $Q \in \mathbb{R}^m$ such that $\mathbb{R}^n \setminus \{P\}$ and $\mathbb{R}^m \setminus \{Q\}$ are homeomorphic. (Since the homeomorphism group of $\mathbb{R}^m$ acts transitively, really any point $Q$ is okay, but I'm trying to be both simple and rigorous.)
Now your proof when $n = 1$ is equivalent to the observation that $\pi_0(\mathbb{R}^1 \setminus \{P\})$ is nontrivial, while $\pi_0(\mathbb{R}^n \setminus \{Q\})$ is zero for all $n > 1$. (Note that $\pi_0(X)$ is in bijection with the set of path-components of $X$, so really we are using that $\mathbb{R}^1$ minus a point is path-connected and $\mathbb{R}^n$ minus a point is not, for $n > 1$.)
When $n =2$, your proof is literally that $\pi_1(\mathbb{R}^2 \setminus \{P\})$ is nonzero whereas $\pi_1(\mathbb{R}^n \setminus \{Q\})$ is zero for all $n > 2$. It is a little questionable to me whether the fundamental group counts as "elementary" -- you certainly have to learn about homotopies and prove some basic results in order to get this.
If you are okay with such things, then it seems to me like you might as well also admit the higher homotopy groups: the point here is that
for all $m \in \mathbb{Z}^+$, $\pi_{m-1}(\mathbb{R}^m \setminus \{P\}) \cong \mathbb{Z}$ whereas for $n > m$, $\pi_{m-1}(\mathbb{R}^n \setminus \{Q\}) = 0$.
If I am remembering correctly, the higher homotopy groups are introduced very early on in J.P. May's A Concise Course in Algebraic Topology and applied to essentially this problem, among others.
[By the way, if we are okay with homotopy, then we probably want to replace $\mathbb{R}^n \setminus \{P\}$ with its homotopy equivalent subspace $S^{n-1}$ throughout. For some reason I decided to avoid mentioning this in the arguments above. If I had, it would have saved me a fair amount of typing...]
Added: Of course one could also use homology groups instead, as others have suggested in the comments. One might argue that homotopy groups are easier to define whereas homology groups are easier to compute. But this one computation of the "lower" homotopy groups of spheres is not very hard, and my guess is that if you want to start from scratch and prove everything, then for this problem homotopy groups will give the shorter approach.
As to why the problem is hard to solve in an elementary way: the point is that the two spaces $\mathbb{R}^m \setminus \{P\}$ and $\mathbb{R}^n \setminus \{Q\}$ look the same when viewed from the lens of general topology. [An exception: one can develop topological dimension theory to tell them apart. For this I recommend the classic text of Hurewicz and Wallman. Whether that's "more elementary", I couldn't say.] In order to distinguish them for $m,n$ not too small, it seems that you need to develop various notions of the "higher connectivities" of a space, which leads inevitably to homotopy groups and co/homology groups.
Another alternative is to throw out homeomorphism and look instead at diffeomorphism. This puts a reasonable array of tools from differentiable topology and manifold theory at your disposal rather quickly (see e.g. Milnor's book Topology from a differentiable viewpoint). It is not hard to show that the dimension of a manifold is a diffeomorphism invariant! So maybe the subtlety comes from insisting on working in the topological category, which often turns out to be more difficult than working with topological spaces with nice additional structures.