Best way to add a search function to user profiles So my client would like to have a search function added to user profiles, because the number is growing rapidly and filtering based on role, etc, isn't working for them.

How do I add a search to the user profile page? This is under User Management > Users > List
You could code up a form_alter() in a custom module that could put search in that admin page.  Or, you could just use www.yourhost.com/search/user to search user accounts.  And if you have advanced search and are using content profiles, you could also restrict your regular node search to that content type, eg type:profile terms to search for in those nodes.