Получается если discover и search это разные запросы, то при поиске по query нельзя отсортировать по жанрам?
Да. Можно только на клиенте отсортировать то, что пришло в ответе.
Т.е. если будет найдено всего 100 результатов, но в ответе 20 на одной первой странице, то отфильтрованы по жарнам будут только эти 20.