You are correct that the search has always been product-centric.
The queries for the search are handled in /includes/modules/pages/advanced_search/header_php.php
The queries for handling product listings are largely driven by the logic in the /includes/index_filters files.
To change the layout of the results delivered by the product search, one would have to adjust the main product-listing, which is handled by the array of output data built by /includes/modules/YOUR_TEMPLATE/product_listing.php and displayed via the /includes/templates/YOUR_TEMPLATE/common/tpl_columnar_display.php (which probably should not be edited without a full understanding of why, since it is used by *many* templates).
By "subset of category images", I suspect you mean you'd like to see something like a listing of subcategory icons, but have the actual list of selected categories be driven by a set of search results instead of by a parent category. Doing that requires, as you've discovered, changing code in several places. The simplest approach would be to adjust the advanced_search/header_php.php file to check whether you're searching "categories" or "products". Then if "categories" is selected, build the appropriate query and stuff its results into the $categories variable (similar to the way the /includes/modules/pages/index/main_template_vars.php in lines 62-126), and then use tpl_modules_category_row.php to render the output (or maybe a modified tpl_index_categories.php).



