I think you need to separate the temperature and efficiency stuff from this and look solely at the true airspeed vs indicated, and make the other variables equal. Keep it simple. At higher altitude, the pressure is less, so there will be less molecules hitting the airframe and pitot tube therefore the indicated speed will be less than at lower altitude. Meanwhile, the aircraft has to travel a greater distance since there are less molecules to hold it back and keep it flying hence why the difference increases as you go higher.
At very high altitudes, the aircraft may barely be flying due to the "thin" air and have a very low indicated speed, all other things being equal, but may have a much higher true airspeed than at lower altitudes since it is covering a much greater distance to meet up with all these molecules that are keeping it flying.
People much smarter than me get advanced degrees in aerodynamics and study all this in detail. If you stop and think about all the variables like prop angles, efficiency, weight, temp, moisture content etc, it could get extremely confusing for a student, so try to look at one thing at a time.
And yes, the airspeed indicater IS lying to you, but it is an error that can be calculated. If I recall, at lower altitudes like what piston singles use, you lose roughly 2% for every 1000 feet you climb. So at 5000 feet, your IAS is 10% less than at sea level.