[Pixel C] [Android Nougat] Play Store fails installing/updating apps - error 495

After updating my stock Pixel C to Android 7.0 via OTA I am unable to either update or install apps from Play Store - error code: 495.

What I have tried:

* Restarting / clearing cache / clearing data for Play Store and Google Services Framework;

* Manually upgrading Play Store to the latest version via apk mirror;

* Removing and re-adding my Google account;

* Factory reset.

Removing/re-adding my Google account or performing a factory reset temporarily fixes the issue - and it apparently triggers a forced Play Store update.

However, as soon as a new Play Store version is released any download starts failing with error 495 again.

This issue has been ongoing since I've upgraded my Pixel C to Android N (a couple of weeks so far), and still unresolved although I've reached out for support anywhere.