Harriman State Park, clocked in at 9.92 miles with 4,344 feet of elevation gain. And my boots were okay, but I'm not overwhelmed by them. At least they didn't give me blisters.
The terrain reminded me of Tennessee in places; hills that look gentle, with almost flat tops, and rocky soil. There was even some mountain laurel. Despite that superficially similar feel, the organization of the hills was different; it's not a plateau with valleys.
The park itself has oodles of trails and is close to the city, so there is a great deal more hiking one could do there. I just bought a book of NYC-area hikes, and I'd like to explore some of the other areas, though - besides the Highline and Central Park, which the book includes.