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

[AC Question]

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 7.0.18 via apk;

* Removing and re-adding my Google account;

* Factory reset.

The latest worked for a few downloads. Afterwards I got the nasty 495 again.