Intuitive basis of Mobius inversion?

Best approach would be to compute the cyclotomic polynomial for $\Phi_n(X)$ by attempting to factorize $X^n-1$, using inclusion-exclusion. You want to get hold of a polynomial with integer coefficients satisfied by, say, 30th roots of unity, which are not roots of unity of lower order (i.e., they are primitive). Then it has to be a factor of $X^{30}-1$. We have to remove 15th roots of unity: So divide out by $X^{15}-1$. But $-1$ is still an undesirable root. So divide out by $X+1$ and continue. You will rediscover this principle.

The inversion formula can be discovered by working with many examples. Write out $f(1) = g(1)$, $f(2) = g(2) + g(1)$, $f(3) = g(3) + g(1)$, $f(4) = g(4) + g(2) + g(1)$, and so on, and then successively solve for $g(n)$ in terms of $f$-values: $$ g(1) = f(1), g(2) = f(2) - f(1), g(3) = f(3) - f(1), g(4) = f(4) - f(2) $$ and so on. With enough data you discover $g(n)$ is a sum of $\pm f(n/d)$ for $d \mid n$ where $d$ is always squarefree. Understanding the pattern in the $\pm$ coefficients leads you eventually to the Moebius function.

The Moebius function is a very unnatural thing when you first see it. There is no way around that. By working with it enough, the function doesn't feel so strange anymore.

The most important property of the Moebius function is that $\mu(1) = 1$ and $\sum_{d \mid n} \mu(d) = 0$ for $n > 1$. These properties in fact characterize it (only one sequence of numbers can fit these conditions). And these are the properties you need to prove Moebius inversion.

There are efficient ways of explaining Moebius inversion using its role as coefficients in the Dirichlet series $1/\zeta(s) = \sum_{n \geq 1} \mu(n)/n^s$, but I don't know if you are familiar with Dirichlet series.