Where can I obtain a complete listing of all NS-based classes?
Xcode -> Help -> Documentation: look under AppKit Reference and Foundation Reference. I'm sure there's similar documentation on apple's dev website.
As far as I recall, the Foundation, AppKit and Core Data frameworks contain all of the non-deprecated NS* classes. You can find the references for Foundation, AppKit, and Core Data on developer.apple.com or in the documentation installed locally with the Apple Developer Tools (use Xcode's Help->Documentation). For a list of all of the "Cocoa" frameworks, start here.
You will find an overview of both Foundation class hierarchy and Application Kit class hierarchy (grouped by topics) in the Cocoa Fundamentals Guide.
There is a free app that Andy Lee wrote that is very useful for quick method reference, called AppKiDo:
http://homepage.mac.com/aglee/downloads/appkido.html
It gives you the option of including individual frameworks in your search results.