For background, I'm a Phoenix native who spent a few years on the east coast and a few more in Nashville, so my thoughts might be similar to your wife's-
1. The sun is very important. Gray, dreary clouds do dampen your mood if you're used to sunshine. Being able to see the horizon is important. Tall buildings or thick, tall trees can make you feel claustrophobic.
2. Not having to shovel snow is very important. If you can't get to work because the roads haven't been plowed and you have a job you have to be at on time, this equals disaster. Not having a garage and not knowing if you'll need to get up an hour early to shovel the car out and shovel the walk gets old pretty fast.
***Alert, the following statements are from my experience only. Take them with a grain of salt.***
3. Nashville is a very fun city for vacation with a lot to see and do. It has a fairly low cost of living, decent freeways, and all the amenities of a big city. The music there is truly incredible.
4. People there "smile through gritted teeth," so they're friendly to your face but don't speak their minds if there's a problem, or at least they don't tell the person who needs to know. Any insult or meanness will be followed with "bless your heart," which is supposed to make the inappropriate comment okay somehow.
5. There's also a large amount of social importance placed on where you attend church, so if you're not religious it will be harder but not impossible to fit in.
6. It's the South. There are a lot of transplants from other areas, so it's not the Deep South, but it's still the south. If you're not white, you're not likely to feel very welcome at times. The neighborhoods can be quite segregated.
7. It's about 50 years behind in terms of gender roles as well. There are exceptions, but many people are surprised to see female physicians and even more surprised when you don't quit your job when you get married so you can raise the kids and have plastic surgery.
8. There is a lot of nature to enjoy and countless gorgeous hikes within a day's drive.
My vote would be for Flagstaff. It's lots of fun, and if there's a cold snap she can always warm up in Phoenix for a few days.