The safest option is to try and start something on the side, get enough traction to be able to pull together a seed round, and then have that new company sponsor your h1b.
However, from what I heard - if you're on H1B you can only work for the company that sponsored your visa. So, the "best option" itself is pretty dicey.
As far as I know, while on a H1B, you can definitely start something on the side, but you can't get a salary for this activity legally. So as long as you are just coding and developing an app, for example is perfectly fine. This can be your 'hobby' and if this 'hobby' gets good traction and you want to convert it to a company then you'll run into all the legal issues pointed here. However, by then if you can convince investors and raise money with a board of directors you are in good shape.
I'm not an immigration lawyer, so those guys will give you the best advice. Please consult one.
Transferring an H1B to a company that the government thinks is legitimate is very straightforward. I was just hoping to outline the steps to getting a company considered legitimate. So if you can get your company off the ground and considered legitimate (the hard part) then you can have your visa transferred to that company (the easy part).
There are certainly employment contract issues -- moonlighting clauses, non-solicitation, and non-compete agreements. But those all apply to anyone building something on the side while employed full-time.
I think the point @karterk was trying to make is that it might be illegal for you to do any paid work at all at your own startup (or any other company other than your original employer), regardless of whether your original employer allows moonlighting or not. I'm not sure how H1B works in the U.S., but a lot of countries have rules like that attached to work visas. So until your visa has been transferred to your startup, your startup can't pay you any salary.
"anyone building something on the side while employed full-time." -- but if your on a H1-B you will always be working full-time, atleast in my case.
if you are working full-time and building something that is not even remotely related to your current full-time job, do those contract issues still apply ?
An H1B holder can't simply move from their sponsoring company to another in the same way that a permanent resident or citizen can, but an H1B can be transferred to another company that also meets all the requirements. There's paperwork involved, but it's definitely possible and legal.
However, from what I heard - if you're on H1B you can only work for the company that sponsored your visa. So, the "best option" itself is pretty dicey.