If you're OK learning on your own, you might try buying a book before committing to the cost of tuition, also. If you really mean "theoretical CS" I don't think you can go wrong with Sipser. The latest edition[1] is expensive, but a used copy of the second edition [2] isn't TOO bad, considering the cost of another few years of education.
[1] http://www.amazon.com/Introduction-Theory-Computation-Michae...
[2] http://www.amazon.com/Introduction-Theory-Computation-Michae...