Why are usually 4x4 gamma matrices used?

You have no other choice than to use $4\times 4$ matrices. All these "representations" are different realizations (related by similarity transformations) of the only possible irreducible representation of the Clifford algebra that is spanned by the abstract $\gamma^\mu$. This representation, in a way, is the definition of what a "Dirac spinor" is, and it is usually a representation of the covering group of the rotation group, but only a projective representation of the rotation group itself. Also, it is not always irreducible as a representation of the rotation group (e.g. the 4D Diac spinor decomposes into the two Weyl spinors and also into two Majorana spinors).

You can show in general that the Clifford algebra in $(1,d-1)$ dimensions has its only irreducible representations given by a vector space of dimension $2^{\lfloor {d/2}\rfloor}$, which is $2^2 = 4$, by considering the "raising/lowering operators" ${\gamma^\pm}^k = \gamma^{2k}\pm\gamma^{2k+1}$ in close analogy to the usual ladder operator method for $\mathfrak{su}(2)$. It turns out that the space spanned by $\lvert s_1,\dots,s_k\rangle $ for $s_i=\pm 1/2$ (the $s_i$ are the eigenvalues of $S^k = [\gamma^{+k},\gamma^{-k}]$) is the only consistent non-trivial irreducible representation you can construct. In odd dimensions, there are two different ones of these that differ by chirality.

Another way uses the group of the $\Gamma^M$ constructed by taking products $\gamma^{\mu_1}\dots\gamma^{\mu_k}$ for $k \leq d$ and $\mu_1 < \mu_2 < \dots \mu_k$. The $M$ runs from $1$ to $2^d$ (another thing one must show...). Any irreducible representation of the Clifford algebra is an irreducible group representation of this group.

Now consider $S = \sum_M \rho(\Gamma^M) N\sigma(\Gamma^M)^{-1}$ for two irreducible representations $\rho$ of dimension $n$ and $\sigma$ of dimension $n'$ and any $n\times n'$-matrix $N$. You can show that $S\rho(\gamma^M) = \sigma(\gamma^M)S$, so $S$ is an intertwiner, and by Schur's lemma either $S$ is invertible, so $n=n'$, or $S=0$. So if there are two different irreducible representations, this says that $\sum_M\rho(\Gamma^M)N\sigma(\Gamma^M)^{-1} = 0$ for any choice of $N$. Therefore $$ \sum_M \rho(\Gamma^M)_{kl}\sigma(\Gamma^M)_{ij} = 0$$ for all $k,l,i,j$. Choosing $k=l$ and $i=j$ summing (i.e. taking the trace of the two matrices independently) and thinking about which gamma matrices contribute to these traces, one can conclude both for the even and the odd case that $n=n'$ must hold, and that there is one irreducible representation for even $d$ and two of them for the odd case.

Thats a nice question. To answer this lets start with clifford algebra generated by $\gamma$ matrices. \begin{equation} \gamma_{\mu}\gamma_{\nu}+ \gamma_{\mu}\gamma_{\nu}=2\eta_{\mu\nu} \end{equation} with $\mu,\nu=0,1,2,\cdots N$ with the metric signature $\eta_{\mu\nu =}\text{diag}(+,-,-,-,\cdots,-)$. Using $I$ and $\gamma_{\mu}$ we can construct a set of matrices as follow \begin{equation} I, \gamma_{\mu},\gamma_{\mu}\gamma_{\nu}\quad(\mu<\nu), \gamma_{\mu}\gamma_{\nu}\gamma_{\lambda}\quad(\mu<\nu<\lambda),\cdots,\gamma_{1}\gamma_{2}\cdots\gamma_{N} \end{equation} There are \begin{equation} \sum_{p=0}^{N}\binom{N}{p} = 2^{N} \end{equation} such matrices. Lets call them $\Gamma_{A}$, where $A$ runs from $0$ to $2^{N}-1$. Now let $\gamma_{\mu}$ are $d\times d$ dimensional irreducible matrices. Our goal is to find a relation between $d$ and $N$. To this end lets define a matrix \begin{equation} S = \sum_{A=0}^{2^N-1}(\Gamma_{A})^{-1}Y\Gamma_{A} \end{equation}. Where $Y$ is some arbitary $d\times d$ matrix. It is follows that \begin{equation} (\Gamma_{B})^{-1}S\Gamma_{B} = \sum_{A=0}^{2^N-1}(\Gamma_{A}\Gamma_{B})^{-1}Y\Gamma_{A}\Gamma_{B} =\sum_{C=0}^{2^N-1}(\Gamma_{C})^{-1}Y\Gamma_{C}=S \end{equation} Where we have used $\Gamma_{A}\Gamma_{B}=\epsilon_{AB}\Gamma_{C}$, with $\epsilon_{AB}^{2}=1$ Hence \begin{equation}S\Gamma_{A}=\Gamma_{A}S\end{equation} Since $S$ commutes with all the matrices in the set, by Schur's lemma we conclude that $S$ must be proportional to the identity matrix so that we can write \begin{equation} S = \sum_{A=0}^{2^N-1}(\Gamma_{A})^{-1}Y\Gamma_{A} = \lambda I \end{equation} Taking trace we get \begin{eqnarray} \text{Tr} S & = & \sum_{A=0}^{2^N-1} \text{Tr} Y = \lambda d\\ \Rightarrow \lambda & = & \frac{2^{N}}{d}\text{Tr} Y \end{eqnarray} or \begin{equation} \sum_{A=0}^{2^N-1}(\Gamma_{A})^{-1}Y\Gamma_{A} = \frac{2^{N}}{d}\text{Tr} Y \end{equation} Taking the $(j; m)$ matrix element of both sides of last equation yield \begin{equation} \sum_{A=0}^{2^N-1}(\Gamma_{A})^{-1})_{jk}(\Gamma_{A})_{km} = \frac{2^{N}}{d}\delta_{jm} \delta_{kl} \end{equation} where $j; k; l; m = 1; 2;\cdots; d$ and we have used the fact that Y is an arbitrary $d \times d$ matrix. If we set $j = k; l = m$ and sum over these two indices, that gives \begin{equation} \sum_{A=0}^{2^N-1} \text{Tr}[(\Gamma_{A})^{-1}] \text{Tr}[\Gamma_{A}] = 2^{N}\end{equation} There are two cases to consider, namely, $N$ even and $N$ odd. For $N = 2M$ (even), $\text{Tr} \Gamma_{A} = 0$ except for $\Gamma_{0} = 1$ for which $\text{Tr} \Gamma_{0} = d$. Which gives \begin{equation} d^2 = 2^N\qquad \text{or} \quad \boxed{d = 2^{N/2}} \end{equation} This is the main result. For four dimensional Minkowski space time $N=4$ cosequntly the dimension of irreducible representation is $d = 2^{4/2} =4$.