Here's a bit of a theory that just popped into my head. I'm probably not the first person to think of this, and it might have been put forth elsewhere in the thread, but here goes:
Pokémon Mansion was the original Cerulean Cave.
Think about it for a second: why is this mansion on Cinnabar Island? Okay, it might have some connection to the research lab in the town, but there's really nothing that ties either to the island. Pokémon Mansion contains all the information about Mewtwo's lore, however, and as you go deeper into the mansion you learn more about Mewtwo. It has a labyrinthine, deep layout stretching across four floors, with lots of wild Pokémon, items, and some trainers. The gimmick with the hidden switches in statues, drops off verandas, and the general size of the place makes it one of the more difficult dungeons to navigate in the game (although thankfully not requiring any HMs - where were the people who designed this place when Gen IV was made?). There are no healing spots either (except in LGPE) and no shortcuts. But the only reason you're sent into this huge and difficult dungeon is to retrieve a key so you can challenge a Gym.
What if Pokémon Mansion was originally meant to be the game's postgame dungeon, with Mewtwo waiting at the end? It would be locked off until you beat the Champion, being unsafe to enter. Lore-wise, it has everything to do with Mewtwo. In the game, it is described as a destroyed mansion once belonging to a scientist, but it could easily have been a destroyed lab instead.
Instead, Cerulean Cave gets the distinction of being Mewtwo's hiding place. But why would it hide in a cave? And what's up with the encounter tables for this cave? OK, it has Golbat and Graveler, but also distinctly non-cave Pokémon such as Magneton, Raichu, Dodrio, Venomoth, Chansey, and Weepinbell. I guess the idea is that Mewtwo attracts these strong Pokémon, but it would make more sense for them to roam a decrepit laboratory ruin than a deep, dark cave.
So, why was Pokémon Mansion put on Cinnabar, and what used to be there? Well, what is Cinnabar Island famous for? Its volcano, of course. It is prominently featured in the Anime, erupts and destroys the town in Gen II, but is nowhere to be seen in Gen I. I think the island was originally supposed to feature a volcano, and you had to traverse it before you could challenge the Gym. The encounter tables for Pokémon Mansion appears to support this: the place is full of Fire-types and the Koffing family (and Rattata and Grimer, but those may have been added after the purpose of the Mansion was changed). It's even the only place you can find Magmar. Sure, the Mansion is supposed to be burnt out, but Magmar's Pokédex entries say nothing about residing in burnt-out buildings. Granted, it is noted for its ability to burn things, and may very well provide a reason for why the Mansion was burned down, but its natural habitats is in volcanoes.
Another piece of information strengthening the theory: Moltres. At the moment, it is sort-of awkwardly dumped in a corner of a room in Victory Road. The other birds were given locations in the depths of optional caves you can access as soon as you get Surf, but Moltres is in a room next to a Trainer halfway through Victory Road. OK, in the Anime it is said to be the protector of the Pokémon League, serving as an Olympic flame of sorts, but it would have made more sense for it to lurk in the optional depths of the Cinnabar volcano. That would have made it available at the same point in the game as the other two birds, in a thematic dungeon filled with other Fire-types. Presumably you would have to climb to the peak of the volcano to challenge Cinnabar Gym, while Moltres would reside in its depths. Or vice versa, I guess: in the Anime, the Gym is in a lava chamber, while Moltres is, after all, a bird.
So what happened? I guess the volcano got scrapped for some reason, possibly because it was too similar to Articuno's hiding spot, or because they didn't have the assets required to make a volcano setting realistic enough to suspend disbelief (with water being the only way to imply running lava), or because they couldn't make the volcano look good enough on the overworld map. This led to the appropriation of Mewtwo's destroyed lab as a dungeon for Cinnabar, with Mewtwo getting a cave for its hideout instead. Moltres was moved to Victory Road for whatever reason, possibly to make players less likely to stumble upon it unprepared while exploring a story-mandated dungeon.
Granted, this is just a theory, but I think all the pieces fit: Mewtwo being in the destroyed lab containing all its lore, Cinnabar getting a dungeon more appropriate to its theme, and Moltres originally having a more comparable location to the other two birds. What do you think?