External Redis connection fails with I/O error despite correct config and passing health checks

Yep, raw TCP services are incompatible with the low-budget shared IPv4 addresses, :raggedy_rabbit:

https://fly.io/docs/networking/services/#shared-ipv4

I don’t know the Redis protocol that well myself, but if you could use TLS/SSL (with SNI) then that would be the best fix:

[[services.ports]]
  handlers = ["tls"]  # ←
  port = 6379