Uma alternativa é transformar as listas de horários em [`set`'s][1] e subtraí-los. Assim, o que sobrar são os horários disponíveis:

```
schedules_dict = {1: ['00:00'], 2: ['00:30', '00:45'], 3: ['00:00', '00:30', '00:45']}
appointments_dict = {1: ['00:00'], 2: ['00:30'], 3: ['00:00', '00:30']}

output = {}
for indice, disponiveis in schedules_dict.items():
    if indice in appointments_dict:
        # vê os horários que sobraram
        sobrou = list(set(disponiveis) - set(appointments_dict[indice]))
        if len(sobrou) > 0:
            output[indice] = sobrou
    else:
        output[indice] = disponiveis

print(output) # {2: ['00:45'], 3: ['00:45']}
```

Um detalhe é que `set` não garante a ordem dos elementos. Se quiser que os horários estejam em ordem, basta trocar para usar [`sorted`][2]:

    sobrou = sorted(set(disponiveis) - set(appointments_dict[indice]))

A princípio, comparar strings contendo dígitos [nem sempre funciona da forma esperada](https://pt.stackoverflow.com/a/440503/112052), mas neste caso os horários estão no formato HH:MM (sempre com 2 dígitos, de acordo com a [norma ISO 8601](https://en.wikipedia.org/wiki/ISO_8601#Times)), então a ordenação é feita corretamente.


  [1]: https://docs.python.org/3/library/functions.html#func-set
  [2]: https://docs.python.org/3/library/functions.html#sorted