Surprisingly, there's some pretty good terrain here in the leftmost tip of the state. Long-distance epics are in short supply but Allegany has some good hiking, Zoar Valley and Letchworth Gorge provide some pretty spectacular scenery (Zoar in particular is a lot more rugged with more "adventure" potential, due to the unfortunate touristization of letchworth) and the obscure, trailless gorges of chautauqua county are beautiful; Arkwright gorge is relatively smaller but offers some great knife-edge mossy ridge hikes and unusual waterfalls, Chautauqua gorge has some spectacular cliffs and ridges, great swimming holes and a steep tributary canyon that features nice waterfalls every 25 feet or so (requires some climbing), and twentymile creek is supposedly the most rugged and least-visited of the bunch. I will be making my first visit(s) this summer.
There are also some gorges above silvercreek I've been meaning to check out.
Given all this as well as Ithaca's "gorges" reputation I really suspect that for mid/western NY, gorge-exploring is really where it's at. Climbing cliffs, scaling waterfalls, splashing in remote swimming holes, and quixotic quests to "find the source" are the delights to be found here; horizontal mileage, not so much.
That said, I've got some ultra-minimalist high-mileage stuff in mind for this summer, for example a trek from fredonia (my hometown) up the arkwright gorge to a rural roadwalk to a swim across lake chautauqua to another roadwalk to a trek down the chautauqua gorge to the lake, then a hike across the lake and back up the canadaway to fredonia, done in 4 days. It's not traditional backpacking fare, but it should be a heck of an adventure! Once one really knows an area the possibilities for outdoor adventure, even where none was previously apparent, come to seem endless.
Extra tip: scan around your area with google maps set to the "terrain" view. When you see deep squiggly lines in the terrain, you're looking at a gorge. Often these gorges, despite having absolutely no reputation as good places for hiking, turn out to be fantastic places to explore. Many of my best experiences in the area came about this way. Sometimes these may involve sneaking onto private property, so ymmv dependent on your personal ethics with regard to that.