Are categories the best way to organize Commerce product filters?
Hard to say if they're the 'best' tool, but I don't see anything here you can't do with Craft categories and they seem the logical and built in way to go about it.  In essence you simply look at your url segments and use these as category filters when retrieving the products
I think so.  It keeps the two separate data concerns nicely separated - but do be aware from a UI point of view, separate category groups are very separate things - you can't use one field to select from both groups (quite a surprise to me the first time I implemented this!)
I think you really only need one template here that simply inspects the url segments and builds the products query from whatever is there.  This part of the question reads a little as if you're confusing the presentation concerns and the data holding concerns (which is not criticism - it's very easy to do!) - your products will live as products over in Commerce, but your actual url routing and display of those at the category level (i.e. the product listing level) - can probably be handled by just one display template.  .  You don't need a 'channel' for these pages as such (they're not pages, rather filtered views).  So probably just a route that points, say, /catalogue/* -> to your one product listing template.  (The actual individual product pages (if they have significantly different displays) - can use multiple templates if need be (or again, conditional logic within the one template)).
There's really no reason that you could not use a route to point say  /products/new to the same template and again inspect the url to build your products query, showing only the newer products.  There's no need per se for a single here unless you want other content on the page or something.


While you described this on slack as a 'noob' question it's not, and it's good to think it through - in some ways this stuff is the hardest part to get your head around with Craft/Commerce.  Once you actually get to implementing it you'll find this bit was actually a lot harder than making it work (well, I did!).

The fact you're using separate urls for everything probably makes it a lot easier than some approaches I think, so nothing in your message really strikes me as unachievable.  The point to understand is that you don't need a channel or section to hold all of these pages - they aren't really pages as such, really they are all views on the same data (all, or some subsets thereof) - you simply have route(s) which point to a single template with logic that inspects the url and filters the products based on that.

More than happy to chat this through more on Slack if that would help.