I have a fully integrated profile search... I cutomized it for my site but it could be customized to return any profile fields as the defaults... say you wanted username, real name, age, and location as the defaults that the results will be listed with, that can be done easily (extra fields will work, too). You can search any profile field... if there were a "has gallery" option, I'm sure we would add that too.
User Search Feature: Type in "new york" and search for records with "new york" anywhere in the profile... you can also select a field to search within.
What we don't have, is a x # of results per page feature... so if you get like 100 results, it takes a second or two to render the table.