Gerry Conway, Rich Buckler and Dick Giordano bring together not only Superman and Captain Marvel, but also Supergirl and Mary Marvel in All New Collectors' Edition C-58 (1978). I didn't own this one as a kid, either. In fact, the last issue of this series that I did buy was the wedding of Lightning Lad and Saturn Girl.
The villain of the story is an evil wizard, Karmang. Once a scientist, he accidentally killed off everyone on his world while searching for a way to gain immortality. He got it, but the guilt drove him insane. Now he plots to destroy Earth-1 and Earth-S, and revives Black Adam and the Sand Superman to aid him. Black Adam was last seen the previous year in Shazam!, but the Sand Superman (Quarmer) had not been seen in about 6 years.
The story gives more play to the supporting cast for Superman, as Captain Marvel's was not an extensive. We see Morgan Edge, Steve Lombard and Lois Lane dealing with missing footage of Superman's most recent fight, with Clark Kent making lame excuses to why he wasn't around to cover it.
Then Superman flies into action to deal with an attack by Captain Marvel. Or at least that it what it looks like. Marvel is really a disguised Black Adam, who has also planted one of two devices that will draw the two Earths together, which will destroy them both.
"Captain Marvel" defeats Superman, and takes off. Superman winds up in a crazed state, lusting for vengeance. Supergirl has shown up by this point and is disturbed by her cousin's behaviour.
Much the same thing then takes place on Earth-2, with Quarmer disguised as Superman, fighting Captain Marvel until that hero loses his cool. And in this case it is Billy Batson's sister, Mary Marvel, who worries about the hero's state of mind.
So Mary follows Captain Marvel and he seeks out and confronts Superman.
As the two men fight, the two women get together and try to make sense of things. Mary Marvel informs Supergirl of Black Adam, and Supergirl tells Mary about the Sand Superman. They figure out that the two men have been lured into battle, but have no idea why. They figure they need to find the villains to get some answers.
And the two guys fight and fight and fight some more. Nice use of Niagara Falls in the background.
Supergirl defeats Black Adam, while Mary simply winds up confronting Sand Superman. He is not inherently a villain, and is content to explain to Mary Marvel what is going on. Mary shares the news of the devices that will destroy their worlds with Supergirl, and they head out to find the real villain.
Meanwhile, the wizard Shazam has managed to contact Captain Marvel and restore his sanity. Marvel allows himself to be defeated by Superman, figuring correctly that this would shock him back into his senses as well. Shazam informs the men of the devices, and they seek them out and destroy them.
But it's Supergirl and Mary Marvel who really save the day, defeating Karmang.
The last page of the story is entertaining. Mary Marvel was quite taken by Superman the moment she met him, and makes a play for him once the battle is over. Supergirl decides to come on to Captain Marvel, and Mary gets all upset. As she rants at Supergirl, she realizes that she has been guilty of the same silly behaviour.
This is the last appearance of the Sand Superman. Black Adam returns a couple of years down the road in the Shazam series in World's Finest Comics.