A few general points from a lawyer who has worked with tech startups for a quarter century in Silicon Valley:
1. If your startup is looking to raise VC funding within the next year or so, consider WSGR or Cooley Godward or any similar large firm that is in NYC. They will be looking for companies they deem "VC fundable" and, if your startup meets this criterion in their judgment, they can and will make valuable introductions to their network of VC firms with whom they deal. This large-firm approach is not particularly flexible but it works very well for the right startups. Their expertise is beyond question, and such firms do offer deferred-fee arrangements as a matter of routine for the right startups.
2. If you are looking to stay more flexible and nimble in how you approach the next year or so, consider a boutique firm that specializes in early-stage tech startups. I don't know the NYC market at this level but would imagine that such firms exist. You will most likely find a good one via referral from other professionals.
A boutique firm will tend to give you much more flexibility in how you approach funding solutions for the company. It is a good option if you do not necessarily want to feel pressured to take on VC funding early on. VC funding at an early stage can be a mixed blessing because that is precisely the point at which you will receive the least favorable terms for your funding.
3. Avoid "wannabe" startup law firms. It seems that all sorts of little firms now want to say that they are startup specialists. A few are but most aren't. If all you see (e.g., on their websites) is marketing lingo couched in very broad terms, you need to be cautious. In general, any law firm worth its salt in the early-stage tech field will be expert in handling the types of issues I discuss here (http://www.grellas.com/faq_business_startup.html - these tutorials may help you quite apart from your search for a law firm, since their goal is to educate founders about early-stage issues in particular). The firm should also be expert in doing funding rounds, IP and e-commerce legal work.
4. Very few startup lawyers will do direct trades of services for equity. It usually is a bad idea for tax reasons for the startup because it puts a high price on your founders' stock and limits your ability to offer quality incentives to your key people.
The much more common practice is a deferred-fee arrangement. Under this type of deal, the firm might extend, say, up to $20K worth of credit for legal services which does not come due until the earlier of some defined time period (e.g., 6 months) or first funding. In exchange for incurring the credit risk, the firm will take some small percentage of founders' stock.