There are only a few episodes of DS9 that I haven't seen, mostly in seasons 1 and 2. I kind of treasure those episodes because it's like a treat, getting to see a new DS9 episode after all these years. That said, Paper Moon was one of those and I went ahead and watched it a few weeks ago. I really enjoyed it. I wasn't crazy about the Vic chcracter, but I like Nog (who doesn't?). I totally agree with your assessment, Nog is the character most 20th century humans can identify with the most. I like that they showed that losing a leg is a big deal, because it is. Likewise, I think it having him get hooked on the holosuite is a lot like the dependence on pain meds that people often develop after serious injuries, but without them having to go there, you know?
Logistically, promising Vic that his program will run all the time seems a little problematic, but it's the last season so whatever. (Doesn't Quark own the holosuites? Why would be be cool with losing profit on renting that one out?)