Of note, we now know that Ho-oh was not among these original 39 species (although Lugia ''was') so it's unclear currently if Game Freak even designed it or the Anime artists did and they decided to Throw It In.
Cutting Pokémon for space is also why Mewtwo is in the Pokedex before Mew. There originally wasn't enough space for Mew, but after removing the debug tools, there was. Had there been enough room it is conceivable that Mew would have been placed before Mewtwo in the Pokedex.
Some also say that Venomoth and Butterfree were inserted into the wrong spaces.
Also, the staff originally wanted to allow the player to pick either a boy or a girl character (the female character that had been designed would actually appear in the first-generation Pokémon Adventures manga), but there was not enough data space available to allow it. Picking your gender wouldn't be implemented until Pokémon Crystal, the sister game to Pokémon Gold and Silver.
Sleeper Hit: Nintendo of Japan actually said It Will Never Catch On while releasing Japanese Red and Green and writing it off as a loss. It didn't top the sales charts, but it kept selling steady in a market where 80% of sales are made in the first two weeks. Game Freak made a few tweaks, released Japanese Blue and Nintendo got their cash cow.
Urban Legend of Zelda: There's a rumor that's been floating around since these games came out about a hacked version known as Pokémon Black (not to be confused with Pokémon Black and White), found on a black-painted cartridge. The player is given a Pokémon known as 'Ghost' instead of one of the starters, and it cannot be put into the PC. It attacks opponents with Curse, and if you return to an area after beating a trainer, it's indicated they died as there's a tombstone present. After beating the game, the player character's Pokémon are all gone and the sprite is swapped for an old man sprite. Going back to Pallet Town results in the character being attacked by the spirits of the Pokemon they killed on their way to beating the game, with the character using Struggle until they die. Its existence is questioned, but a ROM like this does exist online. Article here
A rumor has always been around that when the games were first released in Japan, loads of little children got ill and committed suicide because of the Lavender Town music. Some people thought this was why the music was subtly changed to remove some of the high pitched notes in the American remakes. In reality, the music was changed because people in Japan had been getting headaches from the shrillness of it.
The Missing No (or Missing Number) has had a number of rumors around it, some said catching it would damage your cartridge others say that it would erase your data.
There's a truck sprite that only appears once in the game. The only way to see it is to go way out of your way to avoid triggering a certain plot event that closes off the area and returning when you can travel on water. People believed that it had to have been put there for a reason, leading to hundreds of rumors about this thing. As it turns out, it's just a truck.
Then there's all the rumors about how to catch Mew....
Speaking of Vermilion City, the S.S. Anne was said to return there after the player beat the Elite Four so many times.
Averted in that exploitation of how the game engine processes data will allow you to encounter any monster of your choosing...including Mew.
What Could Have Been: There were many changes, but most notably, there once was a female protagonist◊. She was excluded presumably due to a lack of space for her data and reused for FireRed/LeafGreen as "Leaf".
Her design was used for Blue (known as Green in the US) in the Pokémon manga Pokémon Special.
Professor Oak was originally meant to be the True Final Boss! Though it never happens naturally in the game, you can use a convoluted set of steps to trigger a glitch allowing the Dummied Out fight to occur.
It was originally intended to have 190 Pokémon, though it seems the dropped ones were introduced in Generation II.