When I first purchased AC:O I attempted to run it on my Linux desktop. Unfortunately, nothing happened when I initially tried to launch it. After working through various shenanigans I have found a working combination to play AC:O on Linux.

Note: The performance on Linux is terrible compared to Windows. Everything in this post is true as of February 25, 2019.

  1. Within Steam change the Steam Play version to "Proton 3.16-7 Beta" and restart Steam.
  2. Navigate to your Steam directory in Terminal (default: ~/.steam).
    cd "~/.steam/steamapps/compatdata/812140/pfx/drive_c/Program Files (x86)/Ubisoft/Ubisoft Game Launcher/"
    rm overlay.dll overlay64.dll
    
    Or to do this in one command:
    rm "~/.steam/steamapps/compatdata/812140/pfx/drive_c/Program Files (x86)/Ubisoft/Ubisoft Game Launcher/overlay*"
    
    Note: The overlay from UPlay prevents the game from running. Removing the DLL files will fully mitigate the problem. If you do not rename/delete the DLL files you will encounter the following errors in /var/log/syslog:
Feb 25 12:33:54 desktop steam.desktop[3900]: 2019-02-25 12:33:46 [ 185] [DEBUG] Overlay.cpp (644) : Sending overlay start request
Feb 25 12:33:54 desktop steam.desktop[3900]: 2019-02-25 12:33:46 [ 185] [ERROR] ExceptionShield.cpp (66) : Overlay has detected an unrecoverable error and must shutdown.
Feb 25 12:33:54 desktop steam.desktop[3900]: 2019-02-25 12:33:47 [ 185] [ERROR] ExceptionShield.cpp (66) : Overlay has detected an unrecoverable error and must shutdown.
Feb 25 12:33:54 desktop steam.desktop[3900]: message repeated 2 times: [ 2019-02-25 12:33:47 [ 185] [ERROR] ExceptionShield.cpp (66) : Overlay has detected an unrecoverable error and must shutdown.]
  1. Start the game as usual (from CLI steam steam://rungameid/812140)

Edit April 25: Assassin's Creed Odyssey recently updated and the performance issues appear to be gone. HD quality is now easily achievable. Each time UPlay updates you'll need to rm the overlay DLL files.