You ask:
If you do have [a bijection between morphisms FA → B and morphisms A → GB], then could you not also take your bijection 'in the other direction' between morphisms GA → B in C and morphisms A → FB in D [...]?
This argument doesn’t quite work, since taking the bijection in the other direction, it will go between morphisms A → GB and morphisms FA → B. The functor G still only appears on the codomains of morphisms.
To give a concrete example where no such bijection exists: let (F, U) be the “free group”/“underlying set” functors between Set and Gp.
Now, F is left adjoint to U. But they can’t be adjoint the other way round! If they were, that would give a bijection between $\mathbf{Sets}(U1,\phi)$ and $\mathbf{Gp}(1,F\phi)$ (where $1$ denotes the trivial group, and $\phi$ the empty set). But $\mathbf{Sets}(U1,\phi)$ is empty, while $\mathbf{Gp}(1,F\phi)$ has one element, since $F\phi \cong 1$.
An intuition for adjoints? There’s no easy, one-size-fits-all answer; but a good place to start is with these sorts of free/forgetful examples. Typically one can thing of a left adjoint as adding stuff, as freely as possible — perhaps new elements, perhaps some structure, perhaps imposing some equations if necessary. On the other hand, a right adjoint typically forgets things — forgets structure, sometimes perhaps throws away elements too...
The point you mention that they're a generalisation of inverses is also a good one. The Stanford Encyclopedia of Philosophy calls them “conceptual inverses”, which depending on how you feel about philosophy may be very helpful or not at all.
But really the best way to get intuition for adjoints comes from looking at as many examples as possible; not necessarily all in a hurry, but every now and then, for a while. They’re one of those concepts that doesn't usually come quickly (it didn't for me, nor for anyone I've seen learning category theory), but which — if you give it time to percolate, and occasional exercises — will sooner or later “click” and suddenly seem so natural you can't imagine not understanding it.
Incidentally, a similar question was also asked some time ago at mathoverflow. I very much like the current second answer, giving a rather different example of adjoints: viewing the posets Z and R as categories in the usual way (i.e. there's a unique map x → y whenever x ≤ y), the “ceiling” function R → Z is left adjoint to the inclusion Z → R, while dually the “floor” function is right adjoint to the inclusion. This suggests the slogan: left adjoints round up (again, adding just as much as is needed to get an integer); right adjoints round down (forgetting the non-integer part).
Your first observation has been fleshed out by Bénabou in his paper cited below.
My experience with category theory indicates that the answer to Question A is Yes after removing useless applications of the global axiom of choice, which is used especially in the theorem that fully faithful essentially surjective functors are equivalences. Why useless? Most equivalences of categories in practice appear as adjoint equivalences where the pseudo-inverse functor, as well as unit and counit, are already given.
It is often critized that ZFC doesn't enable us to talk about the category of all functors $\mathsf{Set} \to \mathsf{Set}$. Before moving into more sophisticated foundations (Grothendieck universes, homotopy type theory, etc.), we should first ask ourselves if it is really necessary to talk about this wild category. I would argue that ZFC is not able to formalize all of category theory, but it is able to formalize 99% of category relevant for practice.
The following papers deal with ZFC-foundations of category theory:
Feferman, Solomon, and G. Kreisel. "Set-theoretical foundations of category theory." Reports of the Midwest Category Seminar III. Springer Berlin Heidelberg, 1969.
Bénabou, Jean. "Fibered categories and the foundations of naive category theory." The Journal of Symbolic Logic 50.01 (1985): 10-37.
Shulman, Michael A. "Set theory for category theory." arXiv preprint, arXiv:0810.1279 (2008).
Best Answer
An algebraic example was given in the comments, so here's a topological counterexample.
The forgetful functor $U$ from the category $\mathcal{Top}$ of topological spaces and continuous maps to the category $\mathcal{Set}$ of sets has a left adjoint $D$ which takes a set to the discrete space on that set.
$D$ is fully faithful, since a continuous map between discrete spaces is the same as a function between the underlying sets. More formally, given two sets $X$ and $Y$, every map between $D(X)$ and $D(Y)$ is equal to $D(f)$ for a unique function $f \colon X \to Y$.
However, $U$ is not fully faithful. Given topological spaces $X$ and $Y$, there are (in general) far fewer continuous functions between $X$ and $Y$ than there are functions between $U(X)$ and $U(Y)$.