To be honest, its really not that many. The situation could be greatly improved without removal with: better organizing map categories like I tried to do ("Default" category problem), and folding 2,4,6, and 8 player versions of skirmish maps into one map. I think the redundant maps could be removed entirely, and maybe some of the niche maps like snowflake sea rocks could be a good fit for community maps.
Also, we haven't touched on what is a "quality" map. I think for random maps, playability is the most important aspect, with looks being secondary. However, for skirmish maps, appearance is more important than it is in random maps.
While some random maps do not look pretty, they are quite fun. I think for this reason and others, it would be just fine to have the highest quality maps be front and center to the user, like through quick play, but keep all the maps accessible in game setup and the map browser.
So my issue isn't with organizing and cleaning up maps, its just with the "remove first" approach.