The answer is that the electromagnetic field has two degrees of freedom, corresponding to the two polarizations states of electromagnetic waves. There are multiple methods to derive this using different sets of variables (which all agree). It is important to choose a method and set of variables and work with them consistently, because the calculation (although not the answer) is different with different variables and different methods.
If you work with the field variables, then you start with 6 components $E_i$ and $B_i$ for $i=\{x, y, z\}$. Then as you noted, two of Maxwell's equations are constraint equations. When we choose initial data, we must choose initial data consistent with these constraints. Therefore, we are only free to choose 4 of the original 6 components of $E$ and $B$ independently. Since Maxwell's equations are first order in time (in terms of $E$ and $B$, we effectively have 4 "first order" degrees of freedom. In classical mechanics, this is analogous to giving the position and momentum for two particles. Sometimes it is more intuitive to think in terms of a "second order" formulation. In classical mechanics, this is analogous to saying we need to specify the initial position and velocity of two particles. Then there are two second order degrees of freedom, which correspond to the 2 polarizations of electromagnetic waves.
If you work with potential variables, you start with 4 fields, the scalar potential $\phi$ and the three components of the gauge potential $A_i$. Because of the gauge symmetry, you can do the counting of degrees of freedom in different ways, although you will always get that there are two physical degrees of freedom. One method is to use the Dirac procedure. The first step is to perform a Legendre transformation to compute the conjugate momenta for each field and the Hamiltonian. If you do this, you find that the three $A_i$ are dynamical (have a non-zero conjugate momentum), and the scalar potential $\phi$ is a Lagrange multiplier for a first class constraint. Therefore, the phase space is naively 6 dimensional (3 $A_i$ and 3 conjugate momenta). The constraint itself removes one of these degrees of freedom, and the associated gauge symmetry removes another. Thus, after applying the constraints and accounting for gauge symmetry, the phase space has 4 (first-order) degrees of freedom. This can also be thought of as 2 second-order degrees of freedom, which are the two polarization states of electromagnetic waves.