Eu pessoalmente voto para o Playonlinux . O Playonlinux é um wrapper de vinho de terceiros e possui o script necessário para o AOE2.
Você pode instalar o Playonlinux por
sudo apt-get install playonlinux
depois, no menu de instalação do Playonlinux, escolha Age of Empires 2 e prepare seu disco com o AOE2, depois siga as etapas de instalação na tela.