However, if the S3 keys are larger than ~500mb, then it's not possible to process them in any way with Lambda since there isn't enough "scratch space" available in /tmp.

I was suggesting EFS support merely because it would allow access to arbitrarily large amounts of "local" disk to work with...