Eric,
Starting in the Southern Winds and heading north is an excellent choice for a 500 mile hike. I did it last year, starting at Big Sandy and heading North to Red Lodge, Montana. I called it my “Greater Yellowstone Ecosystem traverse” and would be happy to share my experiences further if you wish. My email is hansberg@msn.com.
Traversing the Winds, dropping into the wilds of Yellowstone, and finishing with a return to lake filled granite mountains in the Beartooths was a tremendous experience.
My primary recommendation: Create your own hike. DO NOT blindly follow the CDT because it is the CDT. There are many examples in the area where the CDT bypasses some of the most inspiring places. Cirque of the Towers and the Thorofare region of Yellowstone come immediately to mind. There are many others. Ponder the topo’s. Imagine what the most beautiful areas are from them. Then, go immerse yourself in all your wise planning.
Enjoy.
Hans