Поскольку для строк операции отрицания нет, мы можем прибегнуть к хитрости: перевести строку в массив чисел, где каждое число - порядковый номер буквы в этом слове:

sorted(data, key = lambda x: (-x[1], [-o for o in map(ord, x[0])]))

Если более наглядно, вот числовое представление слова Ехал:

>>> list(map(ord, data[0][0]))
[1045, 1093, 1072, 1083]

Соответственно, сортировка происходит в обратном порядке. Всё, что остаётся сделать - развернуть все числа в последовательности:

>>> [-o for o in map(ord, x[0])]
[-1045, -1093, -1072, -1083]

В таком случае сортировка будет происходить в обратном лексикографическом порядке.
Результат работы:

>>> sorted(data, key = lambda x: (-x[1], [-o for o in map(ord, x[0])]))
[('Грека', 3),
 ('Руку', 2),
 ('Реку', 2),
 ('Рак', 2),
 ('В', 2),
 ('Через', 1),
 ('Цап', 1),
 ('Сунул', 1),
 ('Реке', 1),
 ('За', 1),
 ('Ехал', 1),
 ('Греку', 1),
 ('Видит', 1)]

Как и было заявлено - список отсортирован в порядке убывания по числу, а внутри групп с одинаковым числом - в обратном лексикографическом порядке.

UPD

Результат сортировки данных из дополнения:

>>> sorted( 
...   data_hard,
...   key = lambda x:
...   (x[0], [-o for o in map(ord, x[1])], [-o for o in map(ord, x[2])])
... )
[('Афанасьев', 'Артём', 'Григорьевич'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич')]

Такой метод задания ключа вполне подходит для решения подобных задач

Ваше решение можно немного сократить:

In [22]: sorted(
    ...:   data_hard,
    ...:   key = lambda x: ([-ord(c) for c in x[0]], x[1], x[2]),
    ...:   reverse=True
    ...: )
Out[22]:
[('Афанасьев', 'Артём', 'Григорьевич'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич')]

Кроме того можно воспользоваться тяжелой артиллерией Pandas:

import pandas as pd

df = pd.DataFrame(data_hard, columns=["last_name", "first_name", "mid_name"])

In [35]: df.sort_values(df.columns.to_list(), ascending=[True, False, False])
Out[35]:
   last_name first_name      mid_name
3  Афанасьев      Артём   Григорьевич
9     Гоголь    Николай    Васильевич
0     Иванов     Сергей     Фёдорович
8     Иванов     Сергей      Петрович
4     Иванов       Иван      Иванович
2     Иванов    Алексей    Евгеньевич
6     Петров     Сергей  Владимирович
5     Петров     Сергей    Викторович
1     Петров  Александр  Владимирович
7     Пушкин  Александр     Сергеевич

в виде списка списков:

In [36]: df.sort_values(df.columns.to_list(), ascending=[True, False, False]).to_numpy().tolist()
Out[36]:
[['Афанасьев', 'Артём', 'Григорьевич'],
 ['Гоголь', 'Николай', 'Васильевич'],
 ['Иванов', 'Сергей', 'Фёдорович'],
 ['Иванов', 'Сергей', 'Петрович'],
 ['Иванов', 'Иван', 'Иванович'],
 ['Иванов', 'Алексей', 'Евгеньевич'],
 ['Петров', 'Сергей', 'Владимирович'],
 ['Петров', 'Сергей', 'Викторович'],
 ['Петров', 'Александр', 'Владимирович'],
 ['Пушкин', 'Александр', 'Сергеевич']]

UPDATE: сравнение разных вариантов по скорости на списке из 10.000 списков:

In [48]: data_big = data * 1000

In [49]: len(data_big)
Out[49]: 10000

In [50]: %%timeit
    ...: sorted(
    ...:   data_big,
    ...:   key = lambda x:
    ...:   (x[0], [-o for o in map(ord, x[1])], [-o for o in map(ord, x[2])])
    ...: )
    ...:
    ...:
53.8 ms ± 220 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [51]: %%timeit
    ...: sorted(sorted(data_big, key=itemgetter(0)), key=itemgetter(1), reverse=True)
    ...:
    ...:
3.66 ms ± 504 ns per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [53]: %%timeit
    ...: sorted(
    ...:   data_big,
    ...:   key = lambda x:
    ...:   (x[0], [-o for o in map(ord, x[1])], [-o for o in map(ord, x[2])])
    ...: )
    ...:
    ...:
54.4 ms ± 797 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [54]: %%timeit
    ...: df = pd.DataFrame(data_big, columns=["last_name", "first_name", "mid_name"])
    ...: df.sort_values(df.columns.to_list(), ascending=[True, False, False]).to_numpy().tolist()
    ...:
    ...:
8.91 ms ± 2.86 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

В сложных случаях сортировать нужно в несколько проходов. Аналогом

sorted(data, key=lambda x: (-x[1], x[0]))

работающим не только с числами, будет

sorted(sorted(data, key=lambda x: x[0]), key=lambda x: x[1], reverse=True)

или для лучшей читаемости

from operator import itemgetter

sorted(sorted(data, key=itemgetter(0)), key=itemgetter(1), reverse=True)

Upd

Пояснение:

Берем вашу таблицу

[('Иванов', 'Сергей', 'Фёдорович'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Афанасьев', 'Артём', 'Григорьевич'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Гоголь', 'Николай', 'Васильевич')]

И упорядочиваем ее по имени

[('Петров', 'Александр', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Афанасьев', 'Артём', 'Григорьевич'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Иванов', 'Сергей', 'Петрович')]

Заметьте, что записи с одинаковыми ключами (именами в данном случае) остались в прежнем порядке относительно друг друга, например, Иванов Сергей Фёдорович стоит раньше Петрова Сергея Векторовича. Это не совпадение, такое поведение гарантируется.

Теперь по фамилии в обратном порядке

data_hard.sort(key=itemgetter(0), reverse=True)

[('Пушкин', 'Александр', 'Сергеевич'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Афанасьев', 'Артём', 'Григорьевич')]

И, опять же, Петров Александр Владимирович идет раньше Петрова Сергея Викторовича, как и в предыдущей таблице. Это значит что результаты предыдущей сортировки не пропали даром. И несмотря на то, что многие записи сменили порядок, потому, что порядок фамилий важнее порядка имен, те записи, порядок которых не нуждался в изменении остались на своих местах.

Это возможно благодаря тому, что алгоритм сортировки используемый в sort и sorted гарантированно устойчивый.

Еще одним (менее производительным) решением будет создание собственного класса-обертки, меняющего операнды сравнения местами.

from functools import total_ordering

@total_ordering
class Reverse:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        return other.value < self.value

    def __eq__(self, other):
        return other.value == self.value

sorted(data, key=lambda x: (Reverse(x[1]), x[0]))

Upd

Пояснение:

Reverse здесь играет ту же роль, что и минус для числел, т.е. является некоторой функцией f такой, что

если x < y, то f(y) < f(x)
если x = y, то f(y) = f(x)

И даже несмотря на то, что этот метод медленнее предыдущего (он использует больше вычислений требующих интерпретации), он все равно более поверхностный, нежели преобразование строки в массив отрицательных чисел, при этом гарантированно корректно работает с любыми типами корректно реализующими сравнение.