What's the fastest (earliest) way to catch Mew in Pokemon Blue/Red?

The fastest I've seen can occur after beating Brock (1^st badge), once you've arrived in Cerulean City. The prerequisites are:

• Have a Pokemon that knows teleport.
  • The earliest you can catch is Abra, just above Cerulean City.
• Have cleared the nugget bridge.
• Have not defeated the trainer to the west of nugget bridge.
• Have not defeated the youngster trainer northeast of the nugget bridge.

The steps are:

• Go to the northern most tip of the nugget bridge, and walk to the grassy path next to the water. Be careful not to trigger the trainer battle there. You'll want to save before attempting, just to be safe, but the goal is to step in front of the trainer to trigger a battle, but open the start menu before the trainer's trigger is raised.

• If the trainer can see you and your menu is open without triggering the battle, you'll want to use teleport.
• From here, go northeast of nugget bridge where all of the trainers are staged on the way to Bill's house.
• Sticking to the northern side of the trail, you'll battle two trainers before arriving in front of a youngster:

• When triggering the battle with the youngster, give some space for the youngster to move from their initial position when the battle is triggered, as demonstrated above.
• After beating the youngster, immediately open your menu and teleport.
• Then, navigate back onto the nugget bridge, as you walk along the bridge, your menu will pop up.
• Close it, and it will trigger an encounter with Mew.

Tutorial Video

If you have the Thunder Badge (3rd badge) from Vermillion City, you can use the trainer fly glitch. Below instructions are summarized from Bulbapedia:

Prerequisites:

• Make sure you have not encountered the Gambler on route 8 or the Youngster on Route 25
• Play until you reach Vermillion City and earn a Thunder Badge
• Teach a Pokémon Fly

Steps:

• Stand directly beneath the Underground Path entrance door on Route 8 so the aforementioned Gambler will be exactly one tile offscreen. (Optional: Save the game so you can reload if you make a mistake)
• Take one step down, and then press and hold the Start button while the step is occurring. The start menu should appear before the gambler "sees" you.
• From the start menu, Fly away (with the most convenient location being Cerulean City). If done correctly, the Gambler will have an exclamation mark above his head, but the Fly animation will begin before he can challenge the player.
• Walk to Route 25 and battle the aforementioned Youngster. You must have at least 1 tile between yourself and the Youngster when the player is spotted, otherwise the game will soft lock.
• Open the start menu and fly to Lavendar Town.
• Head west to return to Route 8. Upon entering the Route, the start menu will appear by itself; closing the menu will immediately begin a battle with a wild Level 7 Mew.

Using the SRAM Glitch/Save Corruption Glitch, it's possible to obtain Mew whilst still in Pallet Town at the very start of the game.

By turning the console off at exactly the right time whilst in the process of saving, party data in SRAM is carried forwards into your save data. By doing this after clearing a save, it will carry forwards all 0xFF bytes - giving you 255 Pokémon in your party. (See here for full info: https://glitchcity.wiki/SRAM_glitch ).

Once you have 255 Pokémon in your party you can enter the Party menu and swap Pokémon around to cause various effects. Swapping one of the first six Pokémon with the tenth will let you have access to the Expanded Item Pack (https://glitchcity.wiki/Expanded_item_pack) - this can ultimately be used for arbitrary code execution, which will let you do almost anything in the game, as in this video, for example:

Full Arbitrary Code Execution like that isn't required for Mew, though. In Pokémon Yellow, you can follow the following steps (with thanks from ChickasaurusGL Evie's helpful video):

1. Perform the SRAM glitch.
2. Swap Pokémon 2 with Pokémon 10.
3. Walk outside to Pallet Town and find Rare Candies hidden deep in the expanded items pack.
4. Use them on Pokémon 1 until Pokémon 1 is level 5.
5. Pokémon 10 now has Mew's sprite.

Here is the video showcasing this in action:

As for the explanation, once you have more than 6 Pokémon the game will read data beyond the original Pokémon list to see what their stats should be. The data for the species of Pokémon number 10 tries to look where the code governing the HP of your first Pokémon is. By levelling it up 5 times, its HP will coincidentally match Mew's index number - hence Pokémon 10 will now appear to be a Mew. According to a person in the video's comments, you can retain the Mew in your party with Pikachu if you deposit and release all 254 other glitchy Pokémon.

This setup is for Pokémon Yellow; a similar setup for Blue and Red should be possible, but would need slightly more advanced modifying of the Pokémon's stats to get to Mew's index number (possibly using HP Ups from the expanded item pack?).