Check BRIN indexs, they are "designed for handling very large tables in which certain columns have some natural correlation with their physical location within the table", I think they fit your needs.
Yes, a BRIN index on the tenant ID would be very useful if the rows in the heap were naturally sorted by the tenant ID, but they are not. They are naturally sorted by their order of insertion, which is completely unrelated. The first step in solving this is to find a way to keep rows belonging to the same tenant close to each other. The second step could be to use a BRIN index.
