I thought it could have been because of a shared CPU at first as well, but I upgraded to dedicated CPUs and it didn't make a difference.

I don't know whether this is a platform issue with Fly or something else, but it was kind of annoying to have such a high variation with seemingly no way to fix it.