Hi Icicle,
You really didn,t mention what kind of climate you are looking for -- We live on Whidbet Island in Washington, have been here for 36 years and for 36 years, I have been waiting for summer !!!
We have been looking at Saint George ,Utah, it,s a beautiful place with many small towns just outside it, and it is right next to Zion National Park -- a very short winter but not nearly as hot as Phoenix !!
Another great place is Prescott, Arizona but it really depends on what you are looking for, and if you,re not retired, you need to think about job opportunities, there being lots of great places to live, but many are very hard to find work !!!
Good luck on your quest, Bill H...