Is there some kind of "package-search" function available for Emacs?

It sounds like M-x package-install should do what you want. If you have helm installed, you will have a helm-like interface to search and install packages. Even without helm, it can be invoked from any buffer, it supports narrowing, and if you do have helm installed, it supports fuzzy matching.

I still tend to use M-x package-list-packages unless I know exactly what I am looking for, because unlike package-install it allows you to see details and descriptions of the packages. I have C-s bound to helm-occur, so I can search through this buffer with a helm-like interface as well. Also, in the *Packages* buffer, you can use f (package-menu-filter) which allows you to narrow down the package list based on a list of comma-separated keywords. However, I can understanding you wanting to avoid the aspects of package-list-packages outlined in your post.