NC applies sales tax by county as well. I created a module that adds counties to the address fields in Checkout. I don't have this on a live site yet, but working on it.

In the addressfield module there is an "Example" module that can be edited to create a sub-administrative-area (county). I have done this for NC and, with maybe an hour of editing, you could turn that into NY. I then wrote rules to apply the approrpriate tax based on the county. The field created on the checkout form with the new module, is required with a default selection as none. If one chooses NC they have to choose a county or the checkout will not go to the next step. IF they choose a different state and still choose a NC county they do not get charged the tax (trying to idiot proof the process). I also exported the rules such that someone could add or edit as needed in a text editor rathe than clinking and adding them through the UI.

As to the City tax, that could be written as a rule. My understanding of the rules thing would require a rule for each City that has its own tax and the appropriate tax added to the checkout process.