Eevee can't evolve into Umbreon or Espeon, actually, due to the absence of time in FireRed/LeafGreen. That means Umbreon and Espeon both have to be traded from R/S/E to be obtained in FireRed/LeafGreen.
In Pokémon FireRed and LeafGreen, however, the time function is completely absent, allowing it to be more like the Generation I games. This also makes it impossible for Eevee to evolve into either Espeon or Umbreon in these games. The same holds true for Pokémon Colosseum and XD, where Espeon and Umbreon are obtainable as Starter Pokémon.
Eevee itself can be found at Celadon Condominiums.