In November, I finished a north-south tour of the Atlantic Coast Route from DC to Charleston, but unlike Litespeed I avoided US17 whenever I could, especially through South Carolina. Much of it had no shoulder or a couple of feet of shoulder at most and I've never been comfortable riding highways without a shoulder. US17 north of Charleston doesn't have anything I would consider to be a shoulder either. In North Carolina, there was a stretch of US17 between Jacksonville and Wilmington that was excellent to ride, until I go close to Wilmington when traffic increased and the shoulder disappeared. From what I saw of US17 in the Carolinas, it seemed like the areas with the heaviest traffic usually had little to no shoulder.
Like others have written though, topography and development limit how much of the ocean you'll get to see. Much of the eastern seaboard is very flat with extensive salt marshes, sounds, and estuaries protected by long, sinuous barrier islands. These features limit the amount and location of roads. Adventure Cycling's route tries to avoid heavily trafficked roads and as a consequence it sometimes has to take a more inland route.