What is the Q-construction, metaphysically? An exact (small) category $P$ is an environment in which we make sense of the "put-together"-edness of objects via (short) exact sequences. It seems like the K-theory of an exact category encodes the high order relations of how objects fit together, but I can't see how the $Q$-construction is the natural medium for this. 
$\bullet$ $0 \to B \to A \to C \to 0$ means that $A$ is put together in some way from $B$ and $C$. Letting $E$ denote the category of short exact sequences in $P$ (with obvious morphisms), we see that this holds in the large as well: If $p$ (resp. $q$) is the projection functor $E \to P$ that sends a s.e.s. to the first (resp. last) object in the sequence, then $(K_i(p), K_i(q)): K_i(E) \to K_i(P) \oplus K_i(P)$ is an isomorphism.
$\bullet$ Moreover, results like devissage, localisation, and resolution are also easily seen  to be reassurances that we are distilling a very sensible notion of put-together-edness.

Can anyone offer a (non-circular) reason as to why the Q-construction is right?

I don't see the sense or utility considering a category in which a morphism from $X$ to $Y$ is an isomorphism of $X$ with an (admissable) subquotient of $Y$.
 A: 1)  One wants the $Q$-construction to have the property that $\pi_1(QP)=K_0(P)$.
2)  To get this, one wants, for any covering space of $BQP$, that $K_0(P)$ acts naturally on the fiber over $0$.
3)  To get this, one wants to associate to any monomorphism $i$ in $P$ a morphism $i_!$ in $QP$ and to any epimorphism $j$ in $P$ a morphism $j^!$ in $QP$ in a way that satisfies certain simple properties; the statement of the properties, and the proof that they suffice to get this result, is in Quillen's Algebraic K-Theory I (Theorem I).
4)  Quillen's $Q$-construction is the Universal construction yielding such $i_!$ and $j^!$.  (The proof is in QUillen's paper, immediately preceding Theorem 1.)
5)  Therefore, there's a sense in which Quillen's $Q$-construction is the natural first guess for what should work.  (Of course the "naturality" of this guess appears only in hindsight; a lot of other people failed to find this construction.)
PS.  After you work through the constructions, you see that this is another way to see the same thing:  For any object $A$ in your category $P$, you want to associate the $K_0$-class $[A]$ to some loop in $BQP$.  The simplest thing to hope for is two canonically defined maps from $0$ to $A$ in $QP$, which together give you your loop.  Quillen's construction provides those two maps (recognizing $0$ as a quotient of both $0\subset A$ and $A\subset A$) in the simplest possible way.
A: There's an interesting motivation in the paper by G. Segal: 
K-homology theory and algebraic K-theory. K-theory and operator algebras (Proc. Conf., Univ. Georgia, Athens, Ga., 1975), pp. 113–127. Lecture Notes in Math., Vol. 575, Springer, Berlin, 1977
It is well-known that the space of Fredholm operators gives a model for
topological K-theory $\Bbb Z \times BU$.  
According to Segal, if $C$ is an exact category, a morphism of the Q-construction $QC$ is akin to a Fredholm operator.
So algebraic K-theory via the Q-construction mimics topological K-theory defined via Fredholm operators.
