I've had the same frustration with S3, and the reasons you went over are what drove me to create this. It seems like they made S3 (10 years ago now?) and just forgot about it. There is no way to sort/filter or even list all the objects in a bucket without writing a recursive algorithm using one of their SDKs.
This does not have to do with AWS Lambda, I'm thinking about renaming it to "functional-s3", or something similar.
To answer your question, there isn't really a workaround for this yet, although indexing should be much quicker than "days". All the keys are listed recursively before running the lambda expression locally. If you have a huge number of files, this can take several minutes, maybe hours depending on the scope.
A workaround I've been considering is using a generator function to list the keys; that way, the lambda expression can start immediately, generating keys as it needs them.
Sure. We have application logs that come in to s3 and are stored by date prefix. I have CRON jobs that run node scripts that do various counts/statistics.