Just a quick note about the Carolinas and Virginia.
(Used to live in Chapel Hill - The Southern part of heaven.)
Althought the Blue Ridge Parkway is lovely, April may be a bit early.
Also, it goes southwest to northeast and you will be trending southeast to northwest.
Much of the immediate coastal area has been built up - condos and golf courses.
To find traditional coastal environments and communities, you have to be inland a bit.
One exception to this is the part of ther Outer Banks protected as National Seashore.
Also, azaleas and other spring flowers will be in bloom.
Some places to consider:
Georgetown, SC - historic with colonial architecture
Okracoke Island, NC on the Outer Banks.
Lovely rides out to ferry at Cedar Island and back to Swan Quarter.
Somerset Plantation on Phelps Lake right next to Pettigrew State Park - camping.
(One of the finest examples of antebellum plantation with preserved slave quarters.)
(Many plantations ignore the rather significant contribution of slaves.)
Edenton is a lovely colonial town on the water - much quieter than Williamsburg.
Merchant's Millpond State Park has rental canoes - can canoe thru cypress swamps.
The Southside of Virginia has great back roads - usually numbered in the 600s and 700s.
Most have very light traffic - although services may be scant.
I would avoid the Norfolk and Richmond areas - really tough to ride thru.
High Bridge State Trail is a possibility - the bridge itself is supposed to open soon.
Maybe head west of there - roughly Courtland to Charlottesville.
If you want to hit a Civil War site - Appomattox is close.
Charlottesville is home to Unive of Va and Monticello - Jefferson's home.
Ocracoke Island, Somerset, and Edenton would give you an excellent feel for the coastal South.
And some of the routes are surprisingly remote for the East Coast.
A few older people on the Outer Banks still speak Hoi Toider - due to former isolation.
Video on this page - http://www.learnnc.org/lp/pages/4811
Feel free to send me any direct questions.
Best - J