You're right, proper transparency support is step 1 -- but that isn't to say that GIMP couldn't have some sort of automatic lossy compression tool (akin to this) on top of that tech.

EDIT: I suppose this software is equivalent to gimp's "Automatically select palette" option when converting images to indexed. Perhaps that option could be replaced with a list of algorithms to choose from, like how the Size dialog lets you choose your own scaling algorithms.

Yes, exactly. This tool is simply because "Automatically select palette" doesn't support transparency. If it did there would be no need for this.

I'm not sure you really need multiple algorithms, the algorithm itself isn't anything special as far as I know - it just supports transparency that's all.

You can get somewhat similar results by selecting all the transparent and partially transparent parts and saving the selection. Then flatten the image (i.e. mix the transparency into the background color), reduce the color depth, then use the color to alpha option only on the selection (not the whole image) to subtract the color and bring back the transparency.

Then count how many colors you have, if you have too many, undo everything, and choose a lower number for color depth and try again. It helps to choose a color that does not otherwise exist in the image for the background mixing color.