I am a recent PhD graduate (mathematics) from Europe, and I am looking for a job in the US. My CV is not that great to get a postdoc or a teaching job at some prestigious university (where they would probably be able to get me a visa). Is there any chance I could get a job at some small college (maybe some small state university or community college) without already having a visa? Will I be able to get a visa if I get accepted as an instructor there?
As far as the official rules are concerned, it does not matter if the petition comes from a well-known university or a community college.
The big problem is that there is significant paperwork involved. Well-known universities that aim to recruit the best qualified students and faculty on a world-wide basis have staff who do that paperwork regularly, and are likely to do it correctly.
A smaller school may not want to get involved in international hiring at all.
I suggest contacting several possible colleges to ask if they sponsor international faculty.
Don't count out a postdoc. Postdocs in the US are often highly reliant on international postgrads, especially in STEM fields. Apply widely, and see what happens. You may have competencies that can be extended to other related fields. Consider your strengths and build up a resume that works to display your practical experience, theoretical background and comprehensive skills. Be sure that this works in English too for your intended audience-- putting things up on Linkedin or a personal website can also work to make you are more attractive candidate. Good luck!