CM13 uses a default password for encryption; not good.
# vdc cryptfs changepw password default_password <NEWPASSWORD>
The Xposed framework seems to be useful for this. The downloader is available in F-Droid. It allows to download the Zip file for SDK23 (Android 6.0), which can then be installed through the bootloader. The FakeGapps module can be installed and activated with with this installer (local copy).
There is an F-droid repository for microG. Once installed, FakeGapps' signature faking should make it happy to pass for the usual Google Play Services libraries.
This allows us to install apps such as LibreSignal.
For background sync (and toast notifications) to work, this also requires enabling device check-ins and Google Cloud Messaging to be enabled, and battery optimisation to be disabled for microG Core.1)