What is the intuition behind the Fontaine-Mazur Conjecture?
Solution 1:
Suppose first that $K$ is a finite extension of some $\mathbb Q_p$, with abs. Galois gp. $G_K$.
A $p$-adic rep. of $G_K$ coming from geometry satisfies some basic conditions: it is pot. semi-stable, and the associated Weil--Deligne rep'n satisfies the Weil conjectures.
There are no other obvious conditions, and my memory (from a talk I saw many years ago, but perhaps it's written somewhere as well) is that Fontaine conjectured that these necessary conditions should be sufficient for an irred. $p$-adic rep. of $G_K$ to come from geometry. In the case when the rep'n looks like it should actually come from an abelian variety, I believe you can use Honda--Tate theory (and maybe some further related tools) to prove the conjecture, which gives some confidence in the general case.
In the global case, one again has the obvious necessary conditions: finitely many ramified primes, pot. semi-stable locally at primes above $p$, and the Weil conjectures.
Again, there were no other obvious necessary conditions, and so, building on one's confidence in the local conjecture, it is natural to guess that they are also sufficient in the global context.
When Fontaine and Mazur were discussing this (the early 90's, I guess) Mazur pointed out that the condition on the Weil conjectures was not preserved under deformations, and so was an obstruction to ever proving such results. Mazur knew how to compute the expected dimensions of unrestricted local and global deformation rings, and Fontaine knew (at least in some case, such as the Fontaine--Laffaille case) how to compute the dimensions of local pot. semi-stable deformations rings.
If you imagine that the image of the global def. ring in the local rings meets the pot. semi-stable locus transversely, then you find that the def. space of global reps. that are pot. semi-stable (of some given type and HT weights) is finite, which fits with e.g. the Langlands reciprocity conjecture. (There are only finitely many Hecke eigenforms of fixed weight and level.)
These sorts of computations (I think there might be one in the original FM article) suggest that the conjecture might be true even without assuming the Galois rep. satisfies the Weil conjectures, and give more confidence that it is true. To my mind, this deformation theoretic intuition gives pretty non-trivial motivation.
I'm not quite sure exactly how this origin story interacts with Wiles's proof. I'm pretty sure that F and M made their conj. before Wiles's argument appeared, and that deformation theory ideas were part of their motivation yoga. On the other hand, clearly the whole conjecture became a lot more credible after Wiles's results.
As you note, much more is known about the conjecture now than was known when F and M first made their conjecture. This obviously adds to our confidence in it.