Самый простой способ - нарисовать все графики отдельно и указать метку только для первой из каждой категории.
Вот адаптированная версия кода. Я ввел два цикла, которые, надеюсь, облегчают чтение и поддержку кода:
import matplotlib.pyplot as plt
import pandas as pd
cat1_x1,cat1_y1,cat1_x2,cat1_y2,cat2_x1,cat2_y1,cat2_x2,cat2_y2,cat3_x1,cat3_y1,cat3_x2,cat3_y2 =\
'cat1_x1,cat1_y1,cat1_x2,cat1_y2,cat2_x1,cat2_y1,cat2_x2,cat2_y2,cat3_x1,cat3_y1,cat3_x2,cat3_y2'.split(',')
bigdf = pd.DataFrame(columns=[cat1_x1,cat1_y1,cat1_x2,cat1_y2,cat2_x1,cat2_y1,cat2_x2,cat2_y2,cat3_x1,cat3_y1,cat3_x2,cat3_y2])
cats = [[[f'cat{i}_x{j}', f'cat{i}_y{j}'] for j in range(1, 3)] for i in range(1, 4)]
labels = ['Cat 1', 'Cat 2', 'Cat 3']
styles = ['-c*', '-go', '-bs']
for cat, label, style in zip(cats, labels, styles):
for ind, cxy in enumerate(cat):
plt.plot(bigdf[cxy[0]], bigdf[cxy[1]], style, markerfacecolor='none', label=label if ind == 0 else None)
plt.subplots_adjust(left=0.15, right=0.99, top=0.95, bottom=0.19)
plt.legend(loc='best')
plt.show()
![sample plot](https://i.stack.imgur.com/sQUfP.png)