One other thing to help you gain confidence: you should find an instructor who's happy to demonstrate and then let you fly what's sometimes called a "falling leaf" stall (and sometimes isn't). Whatever it's called, the goal is to HOLD the aircraft fully stalled (yoke/stick fully back) for an extended time, GENTLY using the rudder to keep wings level. You can fly like this for as long as your altitude will let you - the descent rate is high (of course) but you are still flying. When you've had enough, yoke forward and fly out of it. The plane will bob up and down as the wings "try" to unstall themselves.
And definitely +1 for doing some basic spin training.