I think the concept of "just search for what you want" is broken.
Instead, the main page should be a hierarchically organized index of all pages on the wiki, and when you want to add something new, the first step should be to edit the main page, and add in a link to what you want to create. Then when you click that link, it will take you to the page to create it. This way, it's really easy to see everything available when you first go to the wiki. Yes, you can click "Special Pages" and then "All Pages", but this is non-obvious and not organized at all.
I'll contribute some stuff whenever I get a camera again...