I don't have a full P.O.A. for you, but I know that the basics of what you're looking for can be handled with core taxonomy and a little creative use of Views. I'm not sure how familiar you are with either of these systems, but basically you'd setup taxonomy vocabularies (categories in the admin menu) for the categories, style, collection, and color that you can tag products with. I'm undecided on if I'd do gender as just the top level category or make the gender be a separate product class... in other words, don't just have a single product node type but have men's apparel and women's apparel be different product classes. This would let you filter products by node type, theme men's and women's product pages differently, setup default size attributes, etc. Also, you could have two separate categories vocabularies and only apply the men's vocabulary to the men's product type and women's to the women's type. However, if this makes it harder to administer/understand the catalog, I don't think it would be worth the trade-off.

With Views, you can create lists of products that can then be sorted by the terms you tag the products with from these various vocabularies. A default View might be a little rough for customers to navigate, but you can do some things to theme the display and use modules like the Views Bonus Pack to present products as a grid of thumbnails w/ prices and such.

So... this is just a few leads, but no full recommendation. I hope it helps.