Believe it or not, there are low-bullshit companies out there. And they are starving for smart, nice, and capable people. Given your visa is tied to your current startup, I would find a way to apply/interview while at your current position for as long as you can.
Meanwhile, I would have a larger conversation with the CEO. What is it exactly that makes working with him/her so hard? Can you discuss with them in a non confrontational manner?
Check out the book Difficult Conversations for help on this: http://www.amazon.com/Difficult-Conversations-Discuss-What-M...