Can you use a materialized view to do the bytea_agg() and then refresh concurrently whenever you need updated data?
The refresh concurrently might take a few hours or days to run to keep the matview up to date, but your queries would be pretty fast.
A possible problem is that you are running out of memory, so the larger queries are going to disk. If you can set up temp space on a faster volume, or bump up your memory configuration it might help.
ie, work_mem, shared_buffers, and file system cache could all play into larger aggregations running faster.