Примерный поиск и сортировка результатов

Да, все верно.

имена и фамилии написаны исключительно на русском?

В идеале, может быть написано на любом языке.
Сейчас использую следующий запрос:
$search = array(
'query' => array(
'multi_match' => array(
'fields' => ['name', 'lName'],
'query' => urldecode($_GET['q']),
'fuzziness' => 'auto',
),
),
);
При помощи чего можно реализовать тот поиск, который Вы описали?