What is the intuitive idea behind looking for a solution of the form an=r^n for a linear homogeneous recurrence relation?
Short answer 1: we know that exponentials satisfy linear recurrences. So we try to fit the linear recurrence to an exponential. We check the result to justify our work a posteriori.
Short answer 2: someone has worked this method out in the past, so we use it.
Medium answer: we can write a linear recurrence relation as a matrix equation
$$ v_{n+1} = A v_n $$
where $v_n$ is a vector whose components are consecutive terms of the linear recurrence. This is easy to solve:
$$ v_n = A^n v_0 $$
If $A$ is diagonalizable, we can obtain a closed form for $v_n$ by diagonalizing and computing the exponential.
Long answer: there is a theory of difference equations that is quite analogous to the theory of differential equations. Given a function $f$, we define the (forward) difference $\Delta f$ to be the function $(\Delta f)(n) = f(n+1) - f(n)$. Many things in the theory of differential calculus have analogs in this difference calculus.
For example, the analog of the fundamental theorem of calculus:
$$ \sum_{i=0}^{n-1} (\Delta f)(i) = f(n) - f(0) $$
As in calculus, we learn differences of all sorts of functions. Some are nice:
$$ \Delta(a^n) = (a-1) a^n $$
and some are less nice:
$$ \Delta(x^3) = 3x^2 + 3x + 1 $$
actually, we usually use falling factorials instead of powers of $x$: we define
$$ x^{\underline{n}} = x (x-1) (x-2) \ldots (x-(n-1)) $$
and we have
$$ \Delta(x^{\underline{n}}) = n x^{\underline{n-1}} $$
A linear recurrence can be written as an ordinary difference equation.
Define the forward translation operator $(Ef)(n) = f(n+1)$; or as difference operators $E = \Delta + 1$. Consider the Fibonacci numbers as an example:
$$ f(n+2) = f(n) + f(n+1) $$
can be rewritten as
$$ E^2 f = f + E f $$
which we can solve in an analogous way to how we derive the solution to the analogous differential equation. e.g. we might rewrite it and factor:
$$ (E^2 - E - 1)f = 0 $$ $$ (E - r_1)(E - r_2) f = 0 $$
and solve the difference equation in steps.
(we could rewrite this in terms of $\Delta$ by substituting $E = \Delta + 1$, but leaving it in terms of $E$ is fine too)
Of course, we don't actually do that: like with differential equations, we get introduced to a few recipes for handling common equations, and simply memorize the solution technique. Or if we didn't have it memorized, we might use the guess and check recipe, knowing that the analogous differential equation has its solution as a linear combination of exponentials. (and that exponentials in differential equations are analogous to exponentials in difference equations)