The oldest rock in Virginia, the Nellysford gneiss found in Nelson County, was one of those Cheerios perhaps as much as 1.8 billion years ago.
About 1.2 billion years ago - give or take a few hundred million years - various chunks of continental crust floated into each other. Today, we see those chunks exposed in the central part of Canada and the core of the Blue Ridge Mountains. The correct buzzword for those old Canadian rocks is "North American craton" - but it may be easier to visualize continental plates, floating on the molten mantle 25-50 miles below the surface, as clumps of cereal ("Cheerios" or "Rice Crispies") floating in milk.
When those continental plates drifted together, it was not a gentle bump. Rocks melted in the heat and pressure, and the Grenville Mountains were uplifted. Some of the Rice Krispies joined the North American craton, and the North American plate was enlarged by the rocks that formed the first parts of Virginia. Clumped together, they formed a supercontinent called Rodinia.
At the time, the granite-like rock formed in the collision was not covered with any vegetation. It was barren, and perhaps as rocky as the Maine and Labrador shoreline today. Rain eroded the newly-exposed rock, rivers formed, and erosion carved valleys and built shorelines. Up to 15 miles of rock eroded away, exposing the roots of the mountains formed by the continental plate collisions.1
Once upon a time, the Grenville Event built the core of the Blue Ridge mountains (you can see it exposed in Shenandoah National Park at Old Rag and Mary's Rock) and the State Farm granite northwest of Richmond, under the women's prison in Goochland County. The event (perhaps multiple continental collisions, actually) formed the old "basement" rocks in Virginia. These then began to erode away. One billion years ago, the erosional relief in Virginia (the difference between the mountain peaks and the valleys) may have been roughly 2,000 feet.

That's close to the 1,000-2,000 feet of erosional relief that typically you see today from the Blue Ridge, looking west towards the Shenandoah Valley or east towards the Piedmont. Skyline Drive may be nearly 4,000 feet high in places... but the adjacent territory is also about 2,000 feet above sea level, so the "relief" (the difference in elevation between two points) is usually less than 2,000 feet.
Several hundred million years later, those two continental plates drifted apart. The mantle bubbled a little (or a spoon swirled...), a crack formed, and one plate drifted away from the other. First debris from ridges on both side of the crack eroded into it, then finally salty ocean water filled the crack. Instead of being smushed between two continents, Virginia emerged on the coastline of the North American craton.
This bumping and bouncing by continents is still going on today, incidentally. The rift valley in East Africa is a crack that's still all dry land, but you can see the ocean invading between Africa and Arabia in the crack that we call the Red Sea.
When the continents reversed direction and the crust thinned and then cracked, the Grenville-era granitic rocks on the land were covered by a series of volcanic outpourings of basalt. If you used a straw to blow air gently underneath the Cheerios in your bowl of milk, you can create equivalent eruptions of milk to coat the cereal, the same way the basalt coated the edge of the North American craton.
Basalt is a volcanic rock that is relatively low in quartz (silica), in contract to granite, and can flow fast. It appears the individual basalt flows in Virginia may have moved at rapid (even supersonic) speed up through the Grenville-age rocks. They reached the surface in many cases, poured out, and coated both the hard bedrock and the sediments that had eroded previously. The Grenville-age hills and valleys were covered by about 2,000 feet of basalt, leveling much of the landscape in what became Shenandoah National Park. So the park is covered with "Catoctin basalt" today that erupted nearly 600 million years ago.
Underneath, the core of the Blue Ridge is the Grenville-era rocks, particularly the Pedlar and Lovingston "granites." They're not exactly pure granites in their mineral composition, and they have been metamorphosed (changed by heat and pressure) slightly. However, if you can think of rocks as Cheerios... then we won't bother to split hairs here.
At roughly the same time as the basalts were erupting, a volcano spewed a vast amount of lava near what became the North Carolina border. Later, that hard volcanic rock would be buried and exposed again by erosion to become Virginia's highest point, Mount Rodgers.
The basalt lava east of the Blue Ridge appear to have erupted under water. What water? It would have been the Iapetus Ocean, filling in one of the cracks that formed as the Cheerios and Rice Krispies drifted apart.
So imagine you could hop in a time machine at Peaks of Otter on the Parkway, or on Old Rag Mountain in Shenandoah National Park. If you could go back 600 million years, you'd see a flat Virginia plain if you looked towards what's now the Shenandoah Valley to the west. You'd see the Iapetus Ocean to the east. Manassas, Charlottesville, Lynchburg, and Danville would have been beachfront property, or maybe underwater. And the Iapetus coastline of Virginia was twisted 90 degrees from the present orientation, "aligned parallel to the equator that passed through the central part of the United States, roughly coincident with the present-day longitude of Kansas."2
Don't stop now - keep on going to: The Orogeny Zones and Virginia Geology