This is the route we follow for the Great Saunter each year:
https://www.google.com/maps/d/viewer?ll=40.820738,-73.951431&spn=0.239437,0.135718&hl=en&t=m&ctz=240&vpsrc=6&msa=0&source=embed&ie=UTF8&mid=z4WCGoRXvtE8.kdeRI77zKf4A
As you can see, it's possible to come down the West side of Manhattan with few street crossings. There are decent pathways right next to the Hudson, almost all the way. Just hang a right (at 218th ST might be best) after you cross the bridge from the Bronx to Manhattan; get to Inwood Park; and follow the map/Hudson from there.
As the map suggests, it can be a little tricky to try to go left and follow the Harlem River and then the East River, because the pathways are not continuous (yet--eventually there's supposed to be a pedestrian/bike path pretty much around the whole rim of the island). You can still spend a lot of time next to the Harlem, but be aware that you may have to make a couple workarounds. Once you get to the East River, you'll again get to spend a lot of time next to the water (very pleasant)--but I don't think the walkways are done there yet, either, so a couple/few detours are necessary.
If you're feeling energetic you can continue south around the tip of the island and come back up to the Village on the West side, thus avoiding crosstown running.