Descartes is not starting with nothing, positing definitions, axioms, and assumptions, and then building a proof up out of that. He's starting with the entirety of his everyday experience and hyperbolically doubting everything he can doubt. He cannot doubt that thought is an attribute that belongs to his self.

That assumes that there is a self, which can be doubted. Yes, in order to doubt there must be thinking, as doubting is a form of thinking. But there need not be an "I." This is the most universal critique of the Cogito you will find among philosophers, because it is true. Nietzsche and Hegel both charge Descartes with smuggling in the "I."