Erie Canal. The western stretch between Buffalo and maybe Fairport or Palmyra is more paved, civilized and continuous... east of that you have to deal with (or go north around) Syracuse, and you have to go through Utica. Little Falls all the way to Albany is great, mostly paved, the rest stone dust, a few stretches of road, more out there in the wild, so to speak. A great ride no matter which end you pick. To me the eastern part is more adventurous.
Other than the ridges in the Montezuma Wildlife area in the middle of the state and a couple of surprises near Schenectady, the entire thing is pretty flat. Headwinds can be entertaining out west, but that's what the ebike is for!
The GAP trail is on my bucket list as well, but I have done the entire Erie Canal and continue to ride various sections of it every week.