Delaware. It's the friendliest state to "foreign" companies (companies registered in the state but headquartered/operated out-of-state).

You have a nexus with any state in which (1) you are registered or (2) are physically located (employees, offices, facilities, leased real property etc, but not including contract workers or leased equipment). You have to pay income taxes, social security, etc, in those states.

Any law textbook on LLCs.

IMPORTANT: An LLC alone will not shelter you from legal liability. The "piercing the veil" doctrine disregards the LLC and allows someone to go after the owner if the LLC is not sufficiently separated from your personal assets and control. For a sole proprietorship, the control part is already met, so you have to make damn well sure that you keep the LLC assets separate from your personal assets. Log and track EVERYTHING.