slacked on doing 301 redirects as I didn't quite get the gist until it was too late
Never too late to do 301s. You may still be able to recover. Not only it will help Google better understand your new site. By getting the 301s in place you also get to keep your old 'link juice' which you would otherwise lose.
Say, if somebody used to link to this page: example.com/mens-shoes.php the link would no longer help you unless you do 301s
Some awesome tips from @netmeg, I'd just add a little trick I've used on a Magento site I recently finished.
To keep the sorting/options/filters pages out of bots' reach, you can add this to robots.txt
Disallow: *?*=*
From my experience, the filter pages is the biggest Magento stumbling block. One moment you create 50 product pages and the next moment you've got 300 pages with duplicate content :)
Also, about your hierarchy. So, you're saying example.com/shoes/ is blank?
Your category pages are usually very important from the customer journey point of view. See how big retailers use the main category pages to display compelling content and entice people to browse further.
You can create static blocks of custom content (think big images and compelling textual content)
CMS -> Static Blocks
and then apply the Static Blocks via
Catalog -> Manage Categories
the shoe menu the link is javascript:void(0)
Not ideal. Have you given Google an alternative route to be able to navigate and understand your site?
Sounds like you'll have to invest a little bit of $$$ in a custom 'Skin'