I cannot speak to the portion of the trail in/around Syracuse and beyond. I think there's a paved section in the vicinity of Syracuse. I know much of it is unpaved from Syracuse to Fairport. And there are significant portions that don't exist - where you need to follow the road anyhow. As of last year there was contiguous trail from Newark to Lockport, primarily stone dust, but paved in most of Monroe county.
However, if you prefer paved, I would recommend following roads that parallel the canal until you get to Fairport or Pittsford. Between those towns there is a shortish stretch of stone dust, but it is reasonably smooth. And much of the route from Fairport to Greece is paved. From Pittsford through Rochester, to Greece (Long Pond Road) it is paved, after which it becomes stone dust, with varying quality - meaning in some places it may be worth it for the shorter distances and in others it definitely is not.
In this thread: http://www.adventurecycling.org/forums/index.php?topic=7247.0
there is more detail on a route that will keep you near the canal, pass through all the same towns (with their opportunities for services, including, in some cases free showers and camping), and close to the ACA map. Note both the detailed turn-by-turn and my refinement to take you back onto the paved portion of the trail. And in your case you could choose to take the towpath beginning at Fairport or Pittsford, as I already noted. This route does a good job of sticking to roads that are either lightly travelled or have wide paved shoulders.
You can save a fair number of miles if you don't mind driving through southern Rochester, as the canal loops way south, and you can skip the loop. It adds some climb - a bit over 100' - but it isn't steep. It also adds some traffic, so you might consider time of day when choosing whether to cut off the loop. The on-road route (above) makes the cut. If crossing between 9:30 AM and 2:30 PM I wouldn't let the fact you're taking major city streets bother you. Otherwise you may be better off taking the (paved) canal path. It is quite flat: IIRC there are three locks between Fairport and Lockport.
We're about 12 miles off your route, and ride tandem. So we have much the same criteria for route choice, and know this area.