For the first job, mine was at a startup. Founders may be more willing to take a bet on someone who demonstrates passion and an ability to hack on stuff and get it to work, whereas big company hiring seems to be more conservative.
Performing superbly on technical interviews will always get you hired, regardless of your background. If you have a buddy also interviewing, pair up and give each other as many whiteboard interviews as you can (I did 2-3 weeks of 5-6 problems per day). You'll feel much more confident.
Lastly, work on projects you are actually excited about, and interview at places doing stuff you're excited about. That sort of excitement really shines through in an interview. Additionally, it will pay off in quality of life.
Good luck!