Fire man fights Wily Machine's final phase because in Megaman 1, Wily Machine's weakness is Fire Man's weapon.
Cut man fights Mecha Dragon because Cut Man's weapon is a boomerang, as well as Quick Man's, which is strong against Mecha Dragon.
Bomb Man fights Boobeam Trap because in Megaman 2, Boobeam Trap can only be damaged with Crash Bomber.
Elec Man fights Bubble Man because water conducts electricity.
Second game:
Bubble Man fights Wily Machine's final phase because in Megaman 2, Wily's weakness is Bubble Man's weapon.
Metal Man fights Needle Man because their weapons are made of the same material, Ceratanium. Everyone knows what happens when you hit Metal Man with his own weapon, so it's not too far of a stretch to assume the same thing would happen with Needle Man's weapon.
Bubble Man fights Gemini Man because Gemini Man uses his twin as an illusion not unlike a hologram. Bubble Man's weapon is the only thing that can damage the hologram projector in the fight against Wily in Megaman 2. Bubble Lead also crawls along the floor like Gemini Man's weakness, Search Snake. Not to mention, Gemini Man's stage is the closeset thing Megaman 3 has to a water level.
Quick Man fights Shadow Man because the Quick Boomerang beats Metal Man, and Shadow Man (and his weapon) is pretty similar to Metal Man. Also, both Quick Man and Top Man could be considered "speed" types. Top Man beats Shadow Man, and so does the speedster.
Crash Man fights Hard Man because Hard Man's whole thing is meant to be extreme durability, and what better to handle that than a bomb? Also, Hard Man has a pretty predictable and static pattern, which is the perfect thing for a character who uses slow timebombs.
Wood Man fights Spark Man because wood is nonconductive.
Top Man fights Drill Man because their signature attacks involve spinning.
Shadow Man fights Pharaoh Man because Pharaoh Man is stated to be sensitive to intense light due to him working deep in the dark ruins. Now look at Shadow Man's very own namesake. On an inversion, Pharaoh Man's weapon beats the owner of the boomerang weapon, and Shadow Man's weapon is a bladed boomerang. Both are also considered Memetic Badass in their own games.
Spark Man fights Bright Man because both of them are themed around electricity.
Snake Man fights Toad Man because snakes eat toads in real life.
Needle Man fights Skull Man because spikes, not unlike the ones on top of the former's head, is a One-Hit Kill hazard in Megaman games, and skulls are usually used for a symbol of death.
In the third game, Doc Robot's weakness cycle against the bosses make some sense:
Ring Man is weak to Heat Man because the former's weakness in the original game is Pharaoh Shot, which is also a fire weapon.
Dive Man is weak to Bubble Man because both are aquatic robots, and the latter's bubbles can make easy work of the former's Dive Missiles.
Skull Man is weak to Crash Man because Crash Bombs can break through the former's Skull Barrier.
Bright Man is weak to Quick Man as an inversion, because Quick Man is weak to the time-stopping robot from his original game.
Dust Man is weak to Wood Man because of nature vs. wasteland. Not to mention, the latter's weapon can nullify the former's suction attack.
Drill Man is weak to Air Man because like in the latter's original game, his weapon is strong against the robot that uses drill bombs.
Toad Man is weak to Metal Man because the latter's weapon is a sharp blade, and toads (frogs) are usually dissected for biology class.
Pharaoh Man is weak to Flash Man because like in the former's original game, he's weak to the time-stopping weapon.
