I've lived 2 hours from the coast (Fayetteville, NC), near DC (Reston, VA), Michigan (Detroit itself, Detroit Metro area, "Downriver"), and now the Denver area for 4 years.
If you want 4 seasons, CO and NC are not good choices.
North Carolina has a long warm (and hot) season, but very little in terms of cold weather. Access to the ocean is a big plus; just find an area with some interesting geography for other activities; most of NC is pretty flat. You can get away with not owning a snow shovel or heavy winter coat.
Denver is the opposite, with long winters and medium summers; very little in the way of spring and fall. The mountains are absolutely stunning, and in the Denver area you have the juxtaposition of great city activities (concerts, sports, etc) combined with Red Rocks, Garden of the Gods, Royal Gorge, Mesa Verde, and lots of other amazing sights. You have to be fast to catch the trees turning, though, because winter can snap in fast.
For weather, Michigan is great if you don't mind a lot of humidity and cloudy winters (daylight for winter is measured in minutes), just stay away from the huge Detroit Metro area where people are rude and everything is dirty; go up north a bit. There's a ton of outdoorsy stuff to do in the northern Michigan/Upper Peninsula area. You won't get much in the way of hills, though.
Reston (DC) area had a lot of historical stuff to see, and Winter is short but was enough to get the "Winter" experience unless you enjoy skiing/snowboarding. The DC area has many things to see, monuments, historical buildings, great parks and recreation areas, as well as proximity to the ocean, but it doesn't have much in the way of verticality (mtns.) There's a lot of stuff within easy driving reach up and down the coast.
I would recommend living in the Denver area for a couple years. It's worth it for access to the mountains. If you're not tied to an office, you can find cheap, new homes. Houses are expensive only in certain areas (Denver Tech Center, the Federal area, Parker, Downtown, etc.)
I would recommend a year in the DC area for the historical value, but real estate is $$$. Rent and move on.
You can skip Michigan unless you're big into fishing and hunting.
Next time we move, we plan to go back to the East Coast somewhere; maybe Raleigh, NC or something in Virginia.