Why doesn't the plane accelerate/move forward when it's at rest, if the propeller is spinning?
When you start the engine in the c172, the blades on the prop are
  spinning - but the plane doesn't move at all.


When the propellor is idling its obviously moving air, this you can see, feel, and hear, however its simply not spinning fast enough to provide enough thrust to overcome the force of the plane sitting on the ground. Basically this is comprised of friction air resistance as well as some limited brake pressure that is usually applied. With fresh bearings, on level ground an idling prop may very well pull a plane forward. For the record it is a matter of certification that the brakes on an aircraft can hold it in place at full throttle. It also takes a bit more force to get a plane rolling than it does to keep it rolling. You need to break static friction to get rolling but then only provide enough power to overcome kinetic friction. 

Generally speaking static friction is higher than kinetic friction, 


(source)


  When taxiing out, it feels like the forward motion is being provided
  by the wheels - like in a car.


The first time you are in small plane you associate it with a car. You 
equate that feeling with a car and thus you think intuitively that the tires are pushing you. In a car you could not be able to tell the difference between a front wheel drive and real wheel drive setup the idea is the same here. 


  When taking off, you can audibly hear the change with the throttle
  increases. 


I don't think there is a question here. 


  In cruise, the plane almost looks the same from the inside
  as when it's on the ground (i.e. prop spinning). Which is where the
  weird psychological block is for me - the plane feels stationary even
  though the horizon/backdrop is moving towards you, and i get that fear
  kick in that it could drop because there's not enough momentum. 


The plane feels stationary because you are in unaccelerated straight and level flight. In other words the forces are balanced about the aircraft. You feel nothing because there is nothing to feel ("feeling" is really another word for acceleration). This is different than a car, our road system lends its self to speeding up/slowing down often and unless you are on a very straight highway at night when its empty its less likely you are in unaccelerated movement in a car. The twits and turns of the road and the constant passing and slowing down of cars leads to a "feeling" of movement.