Newbie, looking for advice for organizing categories

I am setting up a store using version 1.3.9h. My question relates to the category set up. I am having trouble deciding the best way to organize them.

On paper I have the following categories:
Men
Women
Unisex
Tops
Pants
Skirts
Jackets
Shoes
Accessories

I would like my main navigation to show all those categories, but also have a general Mens link and Womens link. When clicking on the mens link, it would show all the categories for men and the same when clicking on the Womens link.

But I also want this: for example if I click on the Tops link, I am shown all products for men and women together, with a choice in a lefthand column to narrow it down to men or women.

Is it possible to organize my products that way?