The Minneapolis housing market is really easy to get into right now, I have family who just moved up here and they found plenty of good options pretty much immediately. Might be something worth keeping in mind.
What do you not like about CA? As a fellow midwesterner and current Minneapolis resident (who will also be looking for a new job pretty soon), I'm curious to know what it's like out there.