Elementary proof that $\mathbb{R}^n$ is not homeomorphic to $\mathbb{R}^m$

It is very elementary to show that $\mathbb{R}$ isn't homeomorphic to $\mathbb{R}^m$ for $m>1$: subtract a point and use the fact that connectedness is a homeomorphism invariant.

Along similar lines, you can show that $\mathbb{R^2}$ isn't homeomorphic to $\mathbb{R}^m$ for $m>2$ by subtracting a point and checking if the resulting space is simply connected. Still straightforward, but a good deal less elementary.

However, the general result that $\mathbb{R^n}$ isn't homeomorphic to $\mathbb{R^m}$ for $n\neq m$, though intuitively obvious, is usually proved using sophisticated results from algebraic topology, such as invariance of domain or extensions of the Jordan curve theorem.

Is there a more elementary proof of this fact? If not, is there intuition for why a proof is so difficult?

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.