Recommendations for a good (rigorous) text to study Computational Complexity.
Following are my recommendations:


Introduction to Theory of Computation by Michael Sipser. It is an introductory book. Although proofs are complete and not hand waving, but not much maths is needed as a pre requisite. Although Turing machines are covered nicely.
Complexity and cryptography by Talbolt and Welsh. In this book little math background is required. Turing machines is not covered in much details. But the book gives proofs for almost all theorem's it introduces. 
From my experience ( as I am a beginner myself ) Sanjeev Arora and Boaz Barak is the most concise with covering advanced topics like quantum computation etc. Although I think you should have a back ground in probability, number theory to read the part I of the book intended to be for undergraduates, as the book leaves some proofs upto the readers. Again for number theory the book I find readable as ( as there is no pre requisite ) :
Number theory by Willian Stein.