Before moving to Moodle, the sixth-form college in the UK where I used to work used a VLE called Learnwise. Learnwise used a mixture of tabs and buttons for navigation. Teachers needed how-to guides to find their way around. Everyone was very happy when we moved to Moodle. Thus, I don't have any ideas for improving navigation in Moodle based on previous experience, apart from recognising the value of Moodle's navigation bar.
My thoughts are a configurable* drop down menu of all moodles categories would be nice. So you could hide some categories & create alias categories & select courses for the alias category. This could be embedded in the themes header so it sits above the breadcrumb trail. I imagine this is what you've done on moodle.org. I've got a SSI embedded in my themes with CSS 2.0 dropdown menus which works well for ff2+ & ie7+ but i've coded this.
Selecting a category from the drop down menu would simply link to the page listing all the courses in that category.
Alternatively you could have the dropdown menus of categories coming off the breadcrumb trail items, so when you mouseOver Home (the first item in the bread crumb trail) you get a drop down menu of all the top level categories.
*A web interface to configure a row of dropdown menus above the breadcrumb trail.
Jago Brown e-Learning Co-ordinator