Larger theatres, universities, churches, community centers, high schools (particularly if you rehearse in the evenings/weekends). If you have some way of being mutually beneficial to each other that can help- donate theater tickets to a school auction, advertise a business in your program, etc.
Sometimes putting out into the community that you are having trouble finding affordable space will yield results. Ask other small companies in the area where they rehearse!