I have a list of marginals on my site at
http://www.fishpondinfo.com/plants/marginal.htm which includes zones for some of them. There are tons of plants that are hardy in your area. Most of those will die if their roots freeze solid but some can freeze solid like yellow flag iris and sweetflag which are like weeds in my pond.
Hand remove some hair/string algae but don't worry about getting it all. I don't bother with the short algae on the liner. It's filtering the water and providing a microhabitat for all the small animals.
Don't you know that ponds are magnets for leaves and other debris? They all end up in the pond! It doesn't matter if it's well netted or not.
Happy cleaning!