I definitely noticed when the Play Store switched to lossy icons. I can still notice it to this day, though they did at least make it harder to notice (it was especially apparent on low-DPI displays). Fortunately, the apps once installed still seem to use lossless icons.

A lot of images should be lossless. Icons/pictograms/emoji, diagrams and line drawings (when rasterized), screenshots, etc. You can sometimes get away with large-resolution lossy for some of these if you scale it down, but that doesn't necessarily translate into a smaller file size than a lossless image at the intended resolution.

There's another problem with lossy images, which is re-encoding. Any app/site that lets you upload/share an image but also insists on re-encoding it can quickly turn it into pixelated mush.