More frustratingly, though, after using it only a few times I found the nozzle really really stubbornly stuck on.
On my 858D (it should use the same hot air wand as the 8858 as a replacement part), the nozzles actually screw on. There are 2 tiny indents on the nozzle that
have to should be lined up with 2 shallow stamped grooves on the end of the heat gun. It works a lot better when you take the time to look at and line these up when you screw the nozzle on/off vs just blindly jamming it. I learned that after some time, because it is easy to overlook. The indents on the nozzle are so tiny, they are easily dismissed as incidental marks on what looks otherwise like featureless nozzle which must surely rely on a simple slip/friction fit. Yeah, no. And yeah, the nozzle can get jammed from doing it wrong.
I can't seem to find any more nozzles for it than the three it comes with, because most of the nozzles you buy are the ones that tighten with a screw and those don't fit.
The machine screw-tightening nozzles from my other station fit on my 858 just fine. The OD of where the nozzle slips over is exactly the same. There's just those two "threads" which are depressions, and they don't interfere with the fit, whatsoever. So you could buy a set of nozzles with the screw and use those with an 858, AFAIK.

i think i'm comfortable enough with medium size nozzle for everything and its been there like from the beginning. they now rusted i think it will be harder to separate.
I, too, rarely change the nozzle. The medium was on there for over 2 years straight. I just removed and reinserted it. It was gritty, but it UNSCREWED just fine, by hand.
Definitely take a closer look before you resort to something drastic like slotting the back of the nozzles and letting the schmoo out. I, too, was initially frustated, and this idea actually crossed my mind. But upon learning of its presence, the dimples and stamped threads work brilliantly for me. The threads allow you to really settle the nozzle positively into place. With the screw-adjust nozzle, you can get it on there seemingly good, but then it becomes loose and has some wiggle or even falls off after the first bump, because it wasn't seated quite straight to begin with.