If the "New Orleans" appraoch is taken, the two best examples of large barriers constructed post Katrina are the following:
Inner Harbor Navigation Canal Surge Barrier
http://en.wikipedia.org/wiki/IHNC_La..._Surge_Barrier
It is just under 2 miles long, and cost right over a billion. It is not set in very deep water except for the intracoastal waterway crossing, which is maintained at roughly -30 ft.
Gulf Intracoastal Waterway West Closure Complex
http://en.wikipedia.org/wiki/Gulf_In...losure_Complex
This complex is much shorter than the previous one, but contains the largest sector gate in north america and the largest pump station in the world. A serious concern NY would have to address is that if a gate was constructed and closed to keep surge out, there is no switch to turn the Hudson river "off." It will continue to flow, potentially back flooding gated off areas, making massive pumping capacity necessary. Additionally, since NY handles large cargo ships, the gates required would need to be some the biggest and deepest in the world.
A final major consideration that we have dealt with here and that will surely be a concern in NY is the constriction of the tidal prism. Tidal exchange will cause massive currents through the open gates during normal days and tides unless nearly the entire structure is composed of operable gates. In New Orleans, the Army Corps actually damaged the brand new gates they constructed the first time they went to close them due to extreme currents in excess of 20 knots rushing through the gates and slamming them closed. I believe we could engineer and construct whatever we set our minds to, but there are massive environmental trade offs and always unintended consequences of redirecting surge to places that previously haven't flooded due to new flood protection structures.