The West is not for everyone... reading between the lines, I'm thinking you belong in Virginia.
The main question is not where you can live to go hiking---heck most cities have Greenways for hiking---but where you can live which is close to unrestricted backpacking opportunities. "Unrestricted" is the keyword.
No permits, no fees, no reservations, no designated You Must Camp Here madness etc---find these areas and have at it. The TN/NC mountains are still loaded with unrestricted trails and backpacking and camping opportunities---go where you want for however long you want.
I have designs on Utah. My wife wants to stay put in our little town in VA. Not much middle ground there.
It is what it is.
Well, sure, Denver is great in terms of access to mountain hiking, skiing, etc, but it is a big crowded city. We live here though only because we have lots of kids and grandkids here. We (or at least, I) would prefer to live in a smaller "mountain" town, such as Salida or Buena Vista (pronounced by residents bee-une-a-vista!?). Salida is particularly attractive to an old fart like myself because it has a full size, full-service hospital right near town. I search land listings near Salida on a regular basis, and have a cabin plan all ready to go when the time comes. Lots of other really cool towns, like Lake City, Ouray, etc, but we like closer access to Denver (2:15 drive from Salida)
Not sure what Tipi means by "restrictions", but if there are any restrictions to hiking/camping/backpacking in most of CO, I sure don't know of any. Zillions of acres of wilderness (no mechanized anything) and National forests. Except of course in the national parks, which are crowded and need permits, but are cool to visit now and then, but a small percentage of CO hiking terrain. One advantage of having these 4 national parks is that they concentrate the tourists. 90% of the time when we're travelling out of state, and it comes up in conversation that we're from CO, the folks will say: "Yeah! We LOVE Estes Park", meaning they love Rocky Mountain National Park, confusing the little tourist city of Estes Park with RMNP.
Another advantage of CO is that it is centrally located for visiting WY, UT and NM, which all have their charms, especially Utah. Can't say enough good things about southern Utah, except the extreme politics.
A big disadvantage of CO these days, for a good part of the sate (and surrounding states), is the prevalence of beetle kill for pine trees. The good news is the huge percentage of great hiking terrain that is above treeline, but of course you can see the dead forests from there still.
New York State has a ton of opportunities for every outdoor activity imaginable. It also has winter, which is something to consider when moving there from Florida. That being said, I moved to Florida from New York 7 years ago, and if my other half ever decides that she wants to go back, well, I'm outta here. I always took the outdoors for granted when I lived in New York, but never again. I miss it.
Long-distance aspirations with short-distance feet.... :jump