As a NYS native, I am ashamed to admit that tolls were supposed to stop being ccollected in 1997 after an extended bond payment period. That being said, I travelled a ton over it during the last month. I hate the thruway.
If you're coming into the state from Canada, take the 37 exit on the QEW to Queenston/Lewiston (Rt. 405). That will dump you onto 190, which has a quick exit to NYS 31. Routes 31 and 104 are almost parallel to the lakeshore, but end before Albany. I personally like to take 31 as far as I can, say to the Clyde-Savannah area, then drop down to 20, as turtle suggested. Be careful when you drop from the north to 20, however: NYS has a ton of poorly-marked, very low bridges.
It will take you longer, but Governor Dewey would be pleased.