Asheville for sure, DIY Park with indoor park right next door ( if it's open) and 20 miles west on I40 is Waynesville skatepark ( so much fun). My hometown Nashville is good for the Plaza, multiple street spots, Sixth Ave indoor, and a pretty good outdoor park. Just don't plan on finding a cheap hotel near downtown.
If it was me I would do Raleigh, Asheville, Nashville, maybe ATL, Little Rock ( Kanis DIY), Austin, Phoenix, LA.