Gman: The area around Lake City is gorgeous.
http://ghostdepot.com/rg/mainline/marshall route/lakecity.htm
You want solitude? Lake City is the
only town in Hinsdale County, which is 50 miles x 22 miles. Total county population, according to the 2000 census, was 790. Of those, 402 live in Lake City. 95% of the land in Hinsdale County is publicly owned.
The Sangre de Cristos are also stunning.
Grand Mesa is spectacular.
National Parks? I'd recommend Black Canyon of the Gunnison (a single-drop gorge about 2,000' deep) and Great Sand Dunes, on the West side of the Sangre's. Rocky Mountain and Mesa Verde are nice, but get very crowded in the mid-Summer. Mesa Verde is also out in the desert and can get rather hot. Colorado National Monument near Grand Junction is too often ignored in favor of the more popular parks in CO, and one of my favorites is Dinosaur National Monument in the Northwest corner of the state. It is a little warmer and more desert-like there (although in terms of heat, nothing like the Southeast, where you're coming from.)
As for places to camp, there really are literally too many to try and list. Since you like primitive camping, all you really need to do is get some National Forest maps and pick out some likely spots (Google Earth can also be a good help here.) Avoid the Front Range (Pike National Forest and White River National Forest) unless you like crowds - there are about 2.5 million people in the greater Denver metro area and on Summer weekends it seems like they're all up in the Pike and White River national forests.
One thing to keep in mind: Make sure you have a good camp stove. Many areas of Colorado still have an open fire ban in place, which means NO campfires, and they are very strict on enforcing this. After the devastating wildfires of 2002, the state has been very careful about fire issues.
Most of the BLM land is in the North-central (North Park), Northwest, and Southwest parts of the state. The center of the state, where the spine of the rocky mountains runs through, are mostly National Forests.