I think you are on the right path by paying attention to this.
Of course you should start with some keyword research. I think you are correct that Brand is often searched before Type (ie: Nike Running Shoes is probably searched more often than Running Shoes Nike), and certain styles are probably not categorized at all (ie: a person searches for heels , not womens heels), while others are (ie: mens sandals, womens sandals). This, of course, can quickly lead to a problem of a confused hierarchy.
This is where tags can come into play. There will likely be some contradictions where you would have to choose one navigation style over another even though doing so will force you to be less than ideally optimized for one or another. But, if you choose to noindex,follow your navigation and use an optimized tag methodology for your content that is index,follow - you won't have to compromise. Your users will navigate through the site normally, but your search landing pages will actually be tag-based categorization.
This itself can be problematic for a number of reasons, but if you invest well enough into it, the solution can play out very nicely in the long run...
- You will want to "seed" your tag list with keywords that match significant, unique sets of your content.
- You will want to add unique content to each of your tag pages such that they do not overlap too much with other tag pages.
- You will want to limit the total number of tag pages so that you dont have PageRank sprawl (the same huge index issues that faceted navigation can present)
- You will want to try and align your tags with words and phrases for which your users search
- You will have to tag any and all products, but often you can match a category to a tag (ie: womens-shoes/sandals/flip-flops could be automatically taged as "Women's Flip Flops"
Hope this helps put you on the right path!