The problem with H1B visas (at least when I was a manager) was that there was a quota and it was about 3x oversubscribed: so most applicants won't get the visa. (There is a separate queue for people with an MS degree from a US university, but it sounds like that doesn't apply for you).
Have you considered just using a TN-1 visa to get started and then trying to switch to a H1B every year until you pass the lottery? That should make you eligible for employment right away. I think the downside to TN-1 is that it's not considered an immigrant visa, so you can't transition to permanent residency, which is why you would want to continue to transition to H1B once you've gotten employed.
(Interested in what others have to say: maybe my opinion is out-of-date. IANAL.)
Regarding states: the best salaries are in Silicon Valley, obviously, but the taxes and living expenses there are high. If I were looking for work, I'd go to Austin, Texas. The salaries aren't as high but there are still a lot of tech employers and there is no state income tax. You might also consider the Research Triangle Park area in North Carolina.