From the Terminal
Get the Linux version of Steam and enable this in settings
This will unlock the ability to download and install any title even if they are Windows only titles.
Now you'll be able to enable a custom compatibility tool in the settings for the game.
I've been playing the game with Proton 5.8-GE-2-MF which you can get at https://github.com/GloriousEggroll/proton-ge-custom.
You will also need to delete these files to avoid lockups from playing wmv files in-game. Otherwise the game runs flawlessly.
rm -rf ~/.steam/steam/steamapps/common/AoE2DE/resources/_common/movies rm -rf ~/.steam/steam/steamapps/common/AoE2DE/resources/en/campaign/movies
If you are having issues make sure you have the most recent version of DXVK, Proton, Wine and your video card's driver.