Vaguely remembering the events from ALttP, I remembered where to get the flippers to reach the second/third dungeon. The Zora near the witch's house talked about a guy jumping the gap and immediately knew someone was running around with the Pegasus Boots. I continued into to the next few events until I tracked the gem thief down to Kakariko.
It actually took me a dungeon or two after this to understand how to get close to Mr. Speedy. He is immune to bombs, the hookshot, arrows, boomerangs, and everything else in my inventory. Part of me thought the Pegasus Boots were located in some other location, but that just did not make too much sense. I took my hand away from the circle pad, thought it over in my head, and realized to use the merging ability. I felt both accomplished and stupid afterwards.