My friend used to do trail work in northern maine, a lot in Baxter state park, but the part that comes after where the app trail ends. You should know that parts of upstate New York are actually a lot colder than Maine (coastal areas tend to be warmer/more temperate as you may know) That being said, you should just check out Portland or Mid Coast. It's going to be strikingly colder already and if you reeaally want it colder you can move somewhere else from there. I would also suggest Burlington VT or Montreal.