Articuno can be found in the bottom level of the Seafoam Islands after the Strength Boulder puzzle has been completed. For more information, see the FRLG Walkthrough.
Zapdos can be found near the exit to the Power Plant. Surf from the Rock Tunnel PokeCenter to get there. For more information, see the FRLG Walkthrough.
Mewtwo is found at the basement level of the Unknown Dungeon. You need to fix the Time Machine on Island #1 in order to access the Unknown Dungeon. For more information, see the FRLG Walkthrough.
The Defense version of Deoxys can be found by completing the puzzle on Island #9 in LeafGreen only. See the Nintendo Events guide for more information.