Yes, the electrons are in the same state and yes they interact (in the sense that identical bosons interact to create a BEC). The explanation is kind of involved.
In a collection of identical atoms, it's not possible for us to distinguish between them. This also applies to their electrons. This is true whether or not the atoms are cold enough to be in a BEC state.
Now the rules of QM state that when you have identical particles (electrons or atoms) you have to symmetrize over them. Thus a literal answer to your question "But what about the electrons or other fermions of the BEC atoms? Are they in the same state?" is "Yes, they're in the same state but this doesn't have anything to do with the BEC state.
Your second question: "Do electrons of one atom interact with those of another?" can be answered similarly. If you consider the electrons as identical particles which must be symmetrized over, then it is impossible to distinguish one electron from the other. Therefore they must all be in the same state. So anything you do to "one" electron will effect all of them. Therefore they do interact; their waveforms are shared.
Now let's be more specific about your questions in terms of the nature of the BEC state. Consider just a single atom. It is described by a wave function. As the atom is placed in a cooler environment it loses energy. This loss of energy changes the shape of the wave function. It makes the wave function bigger. The wavelength for the wave function of a gas atom is called the "Thermal de Broglie wavelength". The formula is:
$$\lambda_T = \frac{h}{\sqrt{2\pi m k T}}$$
where $h$ is the Planck constant, $k$ is the Boltzmann constant, $T$ is the temperature, and $m$ is the mass of the gas atom.
The thing to note about the above formula is that as the temperature gets lower, the wavelength $\lambda_T$ gets bigger. When you reach the point that the wavelengths are larger than the distances between atoms, you have a BEC. The reference book I've got is "Bose-Einstein Condensation in Dilute Gases" by C. J. Pethick and H. Smith (2008) which has, on page 5:
"An equivalent way of relating the transition [to BEC] temperature to
the particle density is to compare the thermal de Broglie wavelength
$\lambda_T$ with the mean interparticle spacing, which is of the order
$n^{-1/3}$. ... At high temperatures, it is small and the gas behaves
classically. Bose-Einstein condensation in an ideal gas sets in when
the temperature is so low that $\lambda_T$ is comparable to
$n^{-1/3}$."
When the wavelengths are longer than the inter-particle distances, the combined wave function for the atoms (which one must symmetrize by the rules of QM) becomes "coherent". That is, one can no longer treat the wave functions of different atoms as if they were independent.
To illustrate the importance of this, let's discuss the combined wave function of two fermions that are widely separated with individual wave functions $\psi_1(r_1)$ and $\psi_2(r_2)$. For fermions, the combined symmetrized wave function is:
$$\psi(r_1,r_2) = (\psi_1(r_1)\psi_2(r_2) - \psi_1(r_2)\psi_2(r_1))/\sqrt{2}.$$
Now the Pauli exclusion principle says that exchanging two fermions causes the combined wave function to change sign. That's the purpose of the "-" in the above equation; swapping $r_1$ for $r_2$ gives you negative of the wave function before the change.
Another, more immediate, way of stating the Pauli exclusion principle is that you can't find two fermions in the same position. Thus we must have that $\psi(r_a,r_a) = 0$ for any fermion wave function where $r_a$ can be any point in space. But for the case of the combined wave function of two waves that are very distant from one another there is no point $r_a$ where both of the wave functions are not zero (that is, the wave functions do not overlap). Thus the Pauli exclusion principle doesn't make a restriction on the combined wave function in the sense of excluding the possibility that both electrons could appear at the same point. That was already intrinsically required by the fact that the two wave functions were far apart.
Now I used the above argument about "far apart fermions" because the Pauli exclusion principle has a more immediate meaning to a lot of people than the equivalent principle in bosons. The same argument applies to bosons, but in reverse. Bosons prefer to be found near one another, however if we write down the combined wave function for two widely separated bosons, there is still a zero probability of finding both bosons at the same location. Again the reason is the same as in the fermion case: $\psi_1(r_b)$ is only going to be nonzero in places where $\psi_2(r_b)$ is already zero. The bosons are too far apart to interact (in the sense of changing the probability of finding both at the same point from what you'd otherwise expect classically).
Another way of saying all this is that in QM, there is no interaction between things except if their wave functions overlap in space. You use the thermal de Broglie wave function to determine how big a wave function has to be. If the atoms are closer than that, they're interacting in the sense of bose (or fermi) condensates.
So let's apply our understanding to the question "do the electrons interact" in a BEC. Consider the $\lambda_T$ formula to the electron. Since $m$ appears in the denominator, replacing the atom with the electron decreases $m$ by a factor of perhaps 3 or 4 orders of magnitude. This increases $\lambda_T$ by perhaps 2 orders of magnitude. Therefore, any gas which is cold enough to be a BEC will be composed of electrons that are much more than cold enough to also be coherent.
Best Answer
Superfluid helium 4 is the winner here, and by a vast margin. There's a body of literature from the 90s that attempts to estimate the fraction of helium atoms that are Bose condensed in superfluid helium 4. To quote this paper, "These works... estimate the condensate fraction to be ≈7% at saturated vapor pressure (SVP)." At a mass density of 125 g/L, this would give about $10^{24}$ condensed atoms per liter!
Note that while helium liquifies below 4K, you need to go below ~2K to get superfluid helium. The transition from liquid to superfluid is continuous, and so the amount of superfluid helium right at the transition temperature is basically zero. However below about 1K, virtually all helium atoms are in the superfluid state.
That an Avogadro's number or more of atoms can occupy the zero-momentum state of an arbitrarily large box is a pretty remarkable demonstration of Bose-Einstein condensation.
Honorable mentions
Regarding more conventional BECs, the largest I've come across is only slightly larger than the 1 billion you quote in your question; $1.1 \pm 0.6 \times 10^9$ atoms in an earlier paper by the same authors. Most research these days works with only millions of atoms (and rarely hydrogen), so I'm not aware of any efforts to push above billions.
Superconductors have a lot in common with Bose Einstein condensates, since in this effect pairs of fermions also condense into a macroscopic 'supercurrent.' No two fermions can occupy the same state, but if you'll accept the similarities, then there are some theoretical proposals that entire stars can form a "BEC". See e.g. Bose-Einstein Condensate general relativistic stars, though I can't speak to the correctness of this paper.