I finally got out of the hole. I was wrong - in the web iCloud Photo Library I was in fact able to click the first picture in All Photos, hold down Shift, and click the last picture and then select to Download all the pictures and videos. It was again, but it worked - I downloaded the full rez versions from the web, imported them into Photos, then got busy deleting them off the phone. Now I have some working space, I can finish the job by turning off iCloud Photo Library on the phone.
Once all that's done, I believe I can then consider if I want to turn iCloud syncing back on across all three devices. I also discovered I was wrong about the size of iCloud I could get, and I upgraded my account (at least temporarily) to be able to sync the main library back to the web.