First of all, small companies have no more problem applying for H-1B than larger companies. Especially in the last 2 years, where the quotas were not met on day 1 of the application process.
Second, graduate students with a MS have their own special category (not subject to the H-1B cap). And they can use the OPT training program to get a job without having to go through a visa.
Bottom line: check out usvisanews.com, not hackernews, to discuss this.
For one, they have to prove that they (have revenue/are profitable) for X months. If you're a budding Twitter or Facebook in the early days, your revenue is $0 and your profits are also $0 - and that's a red flag to the immigration. And there's other criterias that similar to this where it's easy if you're a big company, but virtually impossible if you're a startup.
OP: Anyway, if you are canadian, it will be easier. There is a special category for canadian who wants to work in US. H1B is tricky. And, it has a quota.
Try those startups who have secured theirs series A, it will be easier to get in.
This isn't nearly the problem you suspect it to be. Just in my field (see my login name), there are many H1B holders occupying jobs that have been certified--by the employer, to the US government--as "unfillable" with a US citizen.
Even the startup visa being debated now, is only meant for "founders" and not for folks who just want to work in a startup.
If you really want to stay in the US without worrying about being kicked out of the country the moment you lose a job, you need to do the time to get a GC (either do a PhD and get the GC faster or get in the queue with the normal folks and wait 10-15 years)