Yes, you can register an LLC or C Corp in any state, but the reason people do things a certain way is usually because of taxes. You don't want to get double taxed (the specifics are nuanced and vary from state to state).

If I were to do it all over again, I would just start out as a DE C Corp.

Yes, and that's probably what you should do, because the other states tend to have weird rules about LLCs.

(I'm in Illinois, have/had NYC parters, operated out of NYC, Chicago, and California, and ultimately sold the company and got to watch a couple hundred thousand dollars in legal and accounting get spent --- like with any serious acquisition --- and neither "DE" nor "LLC" appeared to cause any hiccups for us.)