The Mannahatta Project is constructing maps of what Manhattan was like in 1609, before its "discovery" by Henry Hudson. "The Mannahatta Project will help us to understand, down to the level of one city block, where in Manhattan streams once flowed or where American Chestnuts may have grown, where black bears once marked territories, and where the Lenape fished and hunted." See also The Viele Map of Manhattan.
The Viele Map of Manhattan was made in 1865 and shows the original boundaries and waterways of the city. Here's a thumbnail view (with prints for sale) and the David Rumsey Map Collection has a zoomable version that you can explore. (thx, meg)
Update: Took me forever this morning, but I cobbled together a high-res version of the Viele map from the PITA Java applet on the Rumsey site. Warning: the image is quite large (9859 x 3115, 8.6 Mb) so it might crash your browser if you attempt to look at it...better to save it to a local drive and open it up in an image viewer.
Update: Here's a simple zoomable/scrollable version (a la Google Maps) of the high-res image that I whipped up with Zoomify. Thanks to Aaron for the suggestion.