First of all, let me mention that functional analysis plays a similar role in noncommutative geometry that commutative algebra plays in algebraic geometry, and it pays off to at least have a reference handy. To that end, I recommend "Banach Algebra Techniques in Operator Theory" by Ronald Douglas: it develops the essentials of elementary C* algebra theory completely from scratch (the first chapter is on Banach Spaces). From there, I recommend starting with Higson and Roe's "Analytic K-homology". The book offers a self-contained introduction to C*-algebra theory and operator K-theory and it culminates in a very detailed exposition of the K-homological proof of the Atiyah-Singer index theorem. This is all foundational material in noncommutative geometry in the sense that much of the rest of the subject is organized around these tools.
For example, Connes developed cyclic homology so that he could generalize the Chern character map from topological K-theory (AKA K-theory for commutative C* algebras) to K-theory for noncommutative C*-algebras. Likewise, the inspiration for the the notion of a spectral triple came from the index pairing between K-theory and K-homology: a spectral triple consists of a representation of a C*-algebra on Hilbert space together with an unbounded operator which is compatible with the representation, while a K-homology class is represented by a representation of a C*-algebra on Hilbert space together with a bounded operator which is compatible with the representation. In both cases, the point is to capture some feature of the Atiyah-Singer index theorem and generalize it to the noncommutative setting.
So once you've assimilated enough of Analytic K-homology, it probably wouldn't be quite so hard to go back and tackle some of the literature. Connes' book is of course great with the right background, but you might find his very well written paper "Noncommutative Differential Geometry" easier to tackle. At that point you will have to decide where you want to go: one can dig deeper into noncommutative geometry proper, or one can pursue interactions between noncommutative geometry and conventional geometry and topology. There is also "noncommutative measure theory" built around Von Neumann algebras, but I know much less about that side of things.