Newspapers: fultonhistory.com is primarily NYS. It's a fussy search engine to deal with but they have archived all NYS newspapers and I have gotten a wealth of information from them. Most helpful after about 1900. Don't forget to search with quotes, but I've found surname, town name, date (without quotes) most helpful. If you're subscribed to any of the other national newspapers you may find more. Stuff from Canandaigua & Ontario County is likely to be found in the Rochester Democrat & Chronicle as well, or if the Ontario County resident travels to Rochester for anything.
Church records: I think Canandaigua is part of the Diocese of Rochester. DOR has some genealogy services but I tried them once and never received a response. I have read that the LDS on Westfall Road in Rochester has local church records for DOR.