How about a new TOP verb for relays that would accept filters like REQ does but would return a list of ids of "best" events? I have it implemented on relay.nostr.band for kind 0 and 31990 and used in a couple places already our clients. You would get say top 100 ids and then would load events themselves in batches for pagination.

Requires new code on clients ofc but seems like a good general approach.