Listing Category results with search

Hi Everyone,
Oh man this can be fun when you don’t know what you are doing.

Ok my site wheretonext.co.za will be a directory listing site. I have split my posts into categories for seperate pages of the site eg: category-Church to church page then business to business and so forth.

I have tried loads of plugins to try and get the results I am looking for without much luck.
Currently on the church directory page I am using content views which basically giving what I am looking for on the default look (without the supersize padding!!!) but now I need to be able to add a search to that, I would like to be able to search by name or area or denomination and so forth, but I think just being able to search within the list above would be close enough.

Hope this makes sense lol.

I am also running the site origin plugin to help with layout and virtually no dev knowledge(yet).