Looking for learning resources
Of course, plenty of introductory resources are available and it is impossible to be objective here. So what follows is merely my biased choice.

I would definitely start with reading something on algorithms and on discrete mathematics (possibly in parallel). Here, I would recommend the following books:


Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein
The Design and Analysis of Computer Algorithms, by Aho, Hopcroft and Ullman
Invitation to Discrete Mathematics, by Matoušek and Nešetřil


The first book mentioned is one of the most widely known resources on algorithms, suitable as an introductory resource. The second book is little bit older and more theoretical, however imho still valuable. The third book is (in my opinion) an excellent and readable introduction to various parts of discrete mathematics. 

Later, I would recommend to focus on formal languages and automata theory. Here, my choice is the following book:


Introduction to Automata Theory, Languages, and Computation, by Hopcroft Ullman and Motwani


You might also like to consult the Sipser's book mentioned in one of the comments.

Of course, if you have some background, there may not be a need for you to thoroughly study these textbooks. However, it is imho necessary to have a stable grounding in the above mentioned subjects before proceeding any further. Thus, it may be sensible for you to consult the above mentioned resources and focus on the material that you find new and/or interesting.

After mastering these preliminaries, there are plenty of choices where to continue. In my opinion, you should definitely study some complexity theory. Here, I would recommend the following book:


Computational Complexity, by Papadimitriou


You also might be interested in some slightly more advanced (or, let us say, intermediate) mathematical methods used in the analysis of algorithms. Here, the following resource is considered to be classic:


Concrete Mathematics, by Graham, Knuth and Patashnik


Some basics of optimization (especially linear programming) are a must for computer scientists. Here, I would recommend the following gentle introduction:


Understanding and Using Linear Programming, by Matoušek and Gärtner


A well written (and not very demanding) introduction to randomized algorithms is the following:


Design and Analysis of Randomized Algorithms, by Hromkovič


Finally, some nice books on advanced algorithms and/or computation theory include:


The Design and Analysis of Algorithms, by Kozen
Theory of Computation, by Kozen
Algorithmics for Hard Problems, by Hromkovič
Complexity and Approximation, by Ausiello et al.
Randomized Algorithms, by Motwani and Raghavan


However, I would suggest reading these only after thoroughly mastering those mentioned above.

This is not a complete list, however. Many other excellent resources are available. The selection I have made is based on my personal bias. Moreover, I have included only resources focused on the "algorithmic part" of theoretical computer science. That is, the selection I have made is not only incomplete, but also very narrow.

And I have to mention that learning some more advanced math would be very helpful for you. My general advice is: the more mathematics you know, the better. It is more and more obvious that there is not any mathematics absolutely irrelevant to computer science.