This may look like it's beating a dead horse, but it's not.
All of my Android devices of different brands and different chipsets, from Exynos, Snapdragon 820, Snapdragon 435, with stock or custom ROMs, AOSP-based and manufacturer-based ROMs, all fail to download apps on a fully functional WiFi connection that has no problems with accessing every possible resource that I ever needed.
Updating/Downloading apps fails with Error 495. I had done everything I could to mediate this, but since this is happening on all of the devices that I tried, with more than 1 Google account, it's safe to say that it's not the device's fault.
The fault is in the Downloader app (the one that downloads the apps for Google Play), in communicating with my Asus RT-AC66U router with Asuswrt-Merlin on it. Everything else works fine, including when I connect to another WiFi hotspot on the exact same internet connection. But it also doesn't work if I connect to a WiFi repeater that's hooked up to the same problematic WiFi hotspot on the Asus router. (Both the 2.4 and 5GHz hotspots fail)
Rebooting both routers, and making them go a power-off/on cycle, had no effect. Unhooking the repeater off didn't help either. As I've said, everything works fine. Other WiFi devices on the same hotspot have access to HTTP, HTTPS, with no reported broken keys that would suggest a security risk or anything. I didn't change any settings, and updates used to work just 4 days ago.
So the question is: What is so special about the Downloader app, or about Play store, that makes it the only thing that's failing?
Or how can I diagnose this? Maybe an easy to use packet sniffer that's able to show the failing request and allow me to reproduce it outside of my phone, and figure out what exactly about my router's settings it doesn't like. I promise to share my findings, and will describe in detail every step that I took, if it helps me fix this issue. Because right now I don't even know where to start looking.