Aha, the "imgcnv" tool it mentions has a Windows version which seems to work, and doesn't square-ify the image. You need to edit the Javascript to make it use PNG files and then it works pretty well. I don't have a server handy to upload it to, but the 12752x8816 Castlevania: Aria of Sorrow map turns from one 11.8MB file to 2369 smaller files that add up to 14.7MB after a rather long PNGOUT session.
For the full image, it'd be easiest just to offer it as a separate download (at the cost of server space).
I think it'd be trivial to make it use JPG files for all the scaled down images and PNG for the end, which might make it use a little less space.