All you need is a student visa and having graduated from a US institution in a program longer than 12 months. The fee is only 340$, which is around 10 times lower than an H1-B.
Once you have it, any company can hire you as they would an American citizen or green card holder. 12 months, should be long enough to prove your value to the company/startup so they apply for a green card.
Here is more information on it: http://www.uscis.gov/files/article/OPT_4Apr08.pdf
On top of all that, you're exempt from paying social security and medicare taxes (be sure to notify your employer since some of them are unaware of that fact).
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)
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.
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.
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.
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.