Adding the custom fields and rendering them on specific spots in a template is relatively easy depending on if the custom fields are already supported or the custom fields are, um, custom. Meaning, checkboxes, radio, text areas are supported, things that require repeatable fields would require additional coding to support.
Adding the custom fields can be done by creating an extension that has the fields you require. That would make it upda safe. To display the meta data would require a custom template. Something it appears you already have. So it would just need updated to display the data from the custom fields.
Now, the search, that is called faceted search. That is a bit more complicated … in part, because it is not something built into Connections. Core support is in my plans, but I have not given much thought on the best way to implement it. Off the top of my head … I plan on, very soon, to completely rewrite how Connections queries the entries to be displayed. Part of this would involve making sure, at this low level, results can be limited based on meta data. This alone is a major undertaking, but should pave the way for a decent faceted search which would still need built.
With that said, I think another viable solution would be to query the entry ID/s from the meta data that are being requested via the faceted search and then feed those ID/s into the code that already does processing for querying. This would even be forward compatible with the rewrite I have planned. This could be built as a separate extension.
Probably a bit more detail than what you wanted. I could do this … looking at my current schedule, not until mid March or even into late April though. That can of depends on some others who would be ahead of you if they decide to move forward with the customizations they want.
To give you an estimate on cost. I would needed to know what fields you want added. Where you want the meta data to be displayed in the template and how you want the fields to look. Mockups are great for this. I would also need greater detail on how you would want the custom fields to be shown in the faceted search and how the results should be displayed. Again, mockups would be good for this.