The vector space for the Dirac equation is not 4-dimensional Minkowski space. The quantities that satisfy the Dirac equation are bispinors which are spinor-like quantities that have 4 components. In reality, this is just a combination of two other representations: the "regular" spinor representation (with 2-component spinors) and its conjugate representation. Hence the vector space is going to be the space of such bispinors. However, it is not the spinors themselves that satisfy the Clifford algebra; it's the Dirac matrices. So indeed, the vector space $V$ of the Clifford algebra is the space of $4 \times 4$ complex matrices.
$Q$ is also not the spacetime interval. It is simply the quadratic form for the vector space elements. In a Clifford algebra, the square of an element $v$ is defined as:
\begin{equation}
v^{2} = Q(v)\, I
\end{equation}
where $I$ is the identity element of the algebra (the object which preserves other elements of the group under multiplication). The case of $Q(v) = v^{2}$ is the trivial case one encounters in "regular" algebra. It can however take the form $Q(v) = -v^{2}$ which for example holds true for Grassmann (anti-commuting) numbers. After finding an orthogonal basis in the vector space, if you have $p$ basis elements that satisfy the "regular" quadratic relation and $q$ which behave like Grassmann numbers, then you can write the Clifford algebra symbolically as $Cl_{p,q}(\mathbb{R})$.
The Clifford algebra of the Dirac gamma matrices is $Cl_{1,3}(\mathbb{R})$, which means if we identify those orthogonal elements of $V$, one of them satisfies $e_{0}^{2} = 1$ while the other three satisfy $e_{i}^{2} = -1$. If we perform the analogue of a Wick rotation (or a series of such) on $Cl_{1,3}(\mathbb{R})$, we may turn it into $Cl_{4}(\mathbb{C})$. The same can be done for $Cl_{3,1}(\mathbb{R})$ which satisfies the opposite relations ($e_{0}^{2} = -1$ and $e_{i}^{2} = 1$). Therefore we may choose either of the two with an analogous algebra still in place. It becomes apparent then why the anticommutator of the gamma matrices should be the Minkowski metric $\eta ^{\mu \nu}$: the basis elements match to each of the spacetime components (which of course form an orthogonal basis).
The reason why you are going to have four orthogonal basis elements is due to the dimensionality of the Clifford algebra and the way the Dirac representation of it is constructed. The dimensions of a Clifford algebra of $m$ total elements in $V$ is going to be $2^{m}$. As I mentioned in the first paragraph, the Dirac bispinor representation is the sum of the spinor representation and its conjugate. Since the spinor representation is 2-dimensional, the associated Clifford algebra is 4-dimensional, hence it will have 4 orthogonal basis elements.
You can think of it in terms of the associated group of the Clifford algebra we are examining, which is going to be the Lorentz group $SO(1,3)$. The matrices which shall satisfy the Clifford algebra will combine to form a set of other matrices which obey the Lie algebra of the Lorentz group. Said group can be seen as a manifold of dimensions equal to that of the associated algebra. Every point on the manifold maps to an element of the group, and every such element can be generated by a series of linear infinitesimal transformations, with the unit element of the group as the starting point:
\begin{equation}
g(\alpha) = \mathbb{1} + i \alpha ^{a}T^{a} \, , \quad g \in G
\end{equation}
where $\alpha^{a}$ is a vector of infinitesimal measure ($\alpha ^{2} \approx 0$) and $T^{a}$ are the generators of the algebra. This is how one associates Lie groups to their respective Lie algebras. The Lorentz group for our case that is generated by matrices abiding by the aforementioned Lorentz group Lie algebra, when embedded in 5-dimensional Minkowski space it is going to be a 4-dimensional hyperboloid:

(You may ignore the coordinate tags, I used a Latex graph of mine used in another context).
In that case, the four matrices of the Clifford algebra are the unit matrix and the 3 Pauli matrices $\sigma ^{i}$. These matrices will form the generators of the algebra as a spinor under a Lorentz transformation will transform as such:
\begin{equation}
\Psi _{L} \xrightarrow{\text{$\Lambda$}} e^{-\frac{i}{2} \omega _{\mu \nu} S^{\mu \nu}_{(L)}} \Psi _{L}
\end{equation}
\begin{equation}
\Psi _{R} \xrightarrow{\text{$\Lambda$}} e^{-\frac{i}{2} \omega _{\mu \nu} S^{\mu \nu}_{(R)}} \Psi _{R}
\end{equation}
where $\Psi_{L}$ are the left-handed spinors (spinors in the first of the spinor representations) and $\Psi _{R}$ the spinors in the conjugate representation. The tensorial quantity $\omega _{\mu \nu}$ is a constant while $S^{\mu \nu}$ are the generators of the Lorentz group:
\begin{equation}
S^{ij} = \frac{1}{2} \epsilon ^{ijk} \, \sigma ^{k}
\end{equation}
\begin{equation}
S^{0i} =
\begin{cases}
-\frac{i}{2} \sigma ^{i} \quad , \quad (\text{L}) \\
\frac{i}{2} \sigma ^{i} \quad , \quad (\text{R})
\end{cases}
\end{equation}
If we now combine the left-handed and right-handed spinors into a Dirac (bi)spinor:
\begin{equation}
\Psi _{\alpha} =
\begin{pmatrix}
\Psi_{L} \\
\Psi{R} \\
\end{pmatrix}
\end{equation}
you can see that it will transform similarly under a Lorentz transformation, but its generators will now have to be $4 \times 4$ rather than $2 \times 2$ matrices:
\begin{equation}
S^{\mu \nu} = \frac{i}{4} [\gamma ^{\mu} , \, \gamma ^{\nu}] \Rightarrow
\begin{cases}
&S^{ij} = \frac{1}{2} \epsilon ^{ijk} \,
\begin{pmatrix}
\sigma ^{k} & 0 \\
0 & \sigma ^{k} \\
\end{pmatrix} \\
&S^{0i} = -\frac{i}{2}
\begin{pmatrix}
\sigma ^{i} & 0 \\
0 & -\sigma ^{i} \\
\end{pmatrix}
\end{cases}
\end{equation}