Do it! I'm a NYC'er as well and getting a bike was one of the best decisions I've made recently. The city has gone wild with bike lanes, etc. and you'll be in good company.

And as for storage, a friend suggested something like this to me:

http://www.shelterness.com/diy-bike-wall-storage-racks/

Solves two problems - storage and wall art! ;)