The server is a Hetzner server, based in their Finland datacenter. The client is in Florida. I've tried multiple clients: Apple TV (both native Plex app and Infuse). Also tried iOS Plex app, and iOS Infuse app, as well as a Shield. All with the same results.
Also, I've had other users report the same thing, I'm not sure of all their locations or clients used... but it seems pretty consistent for everyone on the server. So it seems likely to be a server issue.