This has been discussed extensively on the ERE forum, see e.g.
http://earlyretirementextreme.com/wiki/ ... e=ERE_City
http://forum.earlyretirementextreme.com ... hp?id=1299
I think the "optimal" state depends heavily on one's own particular lifestyle and idiosyncrasies so there is no universal answer.
From a libertarian liberty/tax-minimization perspective, I would say New Hampshire or Wyoming are best. Florida, Tennessee, and most of Texas are almost as good. It really depends on your personal breakdown of exposure to income/sales/real estate tax. Utah is in good fiscal shape but is dominated politically by Mormons, which may or may not be a problem.
People with frugal or self-sufficient lifestyles make few taxable transactions, and wind up paying very little tax, even in spite of high tax rates. As some others pointed out, it's possible to live very cheaply in places like NYC and San Francisco if you're willing to make certain compromises.
Your personal climate preferences are a big factor. Would you rather deal with hurricanes or blizzards? Also, your preferred form of recreation. Do you want to be near outdoor activities, or night life, or the ocean, or professional sports teams, or what?
One of my schemes is to own a condo in a ski resort town in Canada, and another in a spring break city in the Southeast US. I'd rent them out on-season, and live in them off-season. E.g. Winter/Spring in Daytona Beach or South Padre Island or something, and Summer/Fall in Quebec. That way I get some rental income, and avoid the worst of the snow and hurricane seasons, and can maintain PPs in two different countries without attracting attention.