No seu exemplo uma lista de tuplas está sendo ordenada. Na lógica atual você está usando o operador `>` para comparar duas tuplas. Isso faz sentido uma vez que uma tupla é uma sequência, e, conforme (tradução livre) da [documentação do Python][2]:

    
> Sequências são comparadas lexicograficamente através da comparação de elementos correspondentes. [...] Coleções que suportam comparações de ordem são ordenadas conforme seus primeiros elementos desiguais (por exemplo, `[1,2,x] <= [1,2,y]` tem o mesmo valor que `x <= y`).

Sabendo disso, o truque para ordenar uma tupla corretamente está em rearranjar os elementos dela conforme seu critério de comparação. No caso, você deseja transformar uma tupla `(nome, idade, media)` em uma tupla `(media, idade, nome`), só e somente para a comparação. 

Assumindo que as médias devem ser ordenadas de maneira descendente e os demais elementos em ordem ascendente a implementação ficaria assim:

    def rearranjar_tupla(tupla):
        return (-tupla[2], tupla[1], tupla[0])
        
    def ordenar(valores):
        tamanho = len(valores) - 1
        troquei = True
        while troquei:
           troquei = False
           for i in range(tamanho):
              if rearranjar_tupla(valores[i]) > rearranjar_tupla(valores[i + 1]):
                trocar(valores, i, i + 1)
                troquei = True
        tamanho -= 1
        return valores 

***[Veja funcionando no Ideone][3]*** 

Se as médias também devem ser ordenadas de maneira ascendente basta inverter as posições da tupla com [*extended slice*][4]:

    def rearranjar_tupla(tupla):
        return tupla[::-1]

***[Veja funcionando no Ideone][5]***

É importante ressaltar porém que, para além de fins de aprendizado, reinventar a roda não costuma ser uma boa ideia. Além do código extra, esse algoritmo de ordenação básico (*Bubble Sort*) é caro do ponto de vista de Complexidade Assintótica (*O(n²)*) e muito ruim do ponto de vista de *cache hits* e administração de memória (múltiplas cópias e *swaps* desnecessários colocam pressão no *Garbage Collector*). 

Os [mecanismos de ordenação da API padrão do Python][6] se valem de um algoritmo bastante robusto chamado [Timsort][7], capaz de ordenar de maneira bem mais eficiente, com Complexidade Assintótica *O(n\*log(n))* no pior caso.

Utilizando a biblioteca padrão do Python podemos substituir todo o código do primeiro exemplo por uma única linha de código: 

    lista.sort(key=lambda x: (-x[2], x[1], x[0]))

***[Veja funcionando no Ideone][8]***
 
---
##Fontes

1. [SOen - How does tuple comparison work in Python?
][1]
1. [The Python Language Reference - Value comparisons][2]
1. [What’s New in Python 2.3 - Extended Slices][4]
1. [Sorting HOW TO][6]
1. [Wikipedia - Timsort][7]

[1]: https://stackoverflow.com/q/5292303/664577 
[2]: https://docs.python.org/3/reference/expressions.html#value-comparisons
[3]: https://ideone.com/ivPOjg
[4]: https://docs.python.org/3/whatsnew/2.3.html#extended-slices
[5]: https://ideone.com/VzzVrX
[6]: https://docs.python.org/3/howto/sorting.html
[7]: https://pt.wikipedia.org/wiki/Timsort
[8]: https://ideone.com/sxdSBw