An update after doing a bunch of experimentation: The stalls are being caused by images larger than about 120K.
There may be a small ramp zone, but images over 150K almost never work (emphasis on almost–occasionally they will process), images under 120K work almost immediately (5 seconds or less), and images in between work at least some of the time.
I’m assuming this is a server issue of some sort, but it’s not a simple case of PHP’s image processing tools choking, since the WordPress install itself is capable of processing large images. I know because some of the images I’m replacing are up into the 3000×2000 pixel range, with file sizes well over 1MB–that’s one of the reasons I’m replacing them.
Anybody ever seen something like this before?