Oh, eu também tenho o AoE 3 e tentei instalar de tudo quanto é jeito (Wine e Cedega) e não tive sucesso.
Acredito que seja algo a ver com o fato do jogo ser da Microsoft, ocorre alguma complicação durante a instalação.
Se alguém já conseguiu, poste aí.