Welcome to America.
Welcome to America.
In the case of a traditional 'offer letter', the envisioned employment is usually ongoing at-will employment. So that 'writing' doesn't create much protection against changing-minds or changing business situations. Either party can end the relationship at any time. ("Welcome to your first morning at work! I regret to inform you we will no longer be needing your services. Good bye.")
You can ask for anything, but in general there's no piece of paper you can get (outside of executive recruiting) in the US that is really going mitigate the risk that the employer can change their mind. You might be able to cover any expenses you incur getting ready to take the new job. If you negotiate that.
In contract law, there's a doctrine called "promissory estoppel" (see http://www.law.cornell.edu/wex/promissory_estoppel) that basically says, "if somebody promises you X, and as a reasonable result of that promise, you do Y, and Y is very bad for you if promise X is revoked, you can sue for damages." The OP's case is a classic example where promissory estoppel can be applied.
Alas, New York does not recognize promissory estoppel (see Marino v. Oakwood Care Center http://caselaw.findlaw.com/ny-supreme-court/1371955.html), but many states do.
It's generally a good thing, too.