Until last year, we lived just outside Rochester, and have ridden Rochester to Niagara Falls (Ontario) several times. Never Buffalo. The tow path is paved from Long Pond Road in Greece through Fairport - essentially where it is passing through the urban portion - and it is more pleasant than going through Rochester, but if you pick the wrong time of day/year, you will find the pedestrians are a significant impediment to progress.
I generally don't ride on the unpaved portions of the towpath. There are parts that are crushed limestone, and parts that are overgrown with grass. And everything in between. The only reason the crushed limestone portions may be faster is if the route is more direct (which it sometimes is) than taking the parallel roads. I don't like the accumulation of dust on the chain, resulting in the need for frequent cleaning.
5 is reasonable as you head from Buffalo toward Rochester; it gradually gets worse as you get into the urban part, and that's where it is nice to catch the towpath. 104 is actually nicer than 5 for much of the distance from just outside Lockport through the vicinity of Holley. But you don't get the canal towns.
There are a number of places along the canal, west of Rochester (there may be more east of Palmyra that I don't know about), where you can spend the night free, and where they may even supply showers. Lockport is listed, on the AC map, haven't tried them; Middleport is nice, includes showers; Holley you have to get there early enough to get the code for the restrooms from someone at the visitors' center before it closes for the day.
Can't speak for anything east of Newark, as I've not ridden that part. Be careful if you get north of the canal in Wayne county or the next one beyond that you don't find yourself going up and down the short dimension of the drumlins. They can be steep and very closely spaced. You get to the top and immediately you're going down the next one, and barely any time to shift gears at the bottom before the climb starts again.