WikiVoyage has a small but clever extension to do quicker lookup of pages in additional content namespaces if no namespace prefix is provided. So if we used this for Commons, and configured "Category:" as an extra lookup namespace, you could type "Low quality chemical diagrams" and it'd pull up the category of that name immediately without the full-text search being loaded. This appears to basically be another solution to https://bugzilla.wikimedia.org/show_bug.cgi?id=11380
The drawback is that it doesn't play nice with autocompletion and other API consumers yet. Ideally I suspect you'd want autcompletion to do lookup in multiple namespaces as well, and provide subtle namespace hinting (as oposed to prefixing) in the dropdown, like so (where CATEGORY would be in a smaller font).
[ Low ] Low quality chemical diagrams CATEGORY Lower Saxony
Thoughts? Would this be a useful improvement for Commons in particular, even without autocompletion? I suspect it could help reduce some of the category/gallery pain.