I would say that your main problem is the age of your battery. Your battery itself is failing less than a cold vehicle being harder to start. Over time batteries lose the ability to charge and hold a charge as well. A car battery generally lasts 3 to 5 years. Lots of short drives could make it fail after 3 if it's not receiving a full charge after starting. It should be mostly charged back up after about 20 minutes. Unless you were causing a heavy electrical load for your alternator.
The hint that tells me this is your real issue is the fact that disabling leaving the headlights on makes a difference on your ability to start your car. Leaving your headlights on has no effect on the temperature of the engine. Only the amount of energy available from the battery at the time of starting in the morning. If you hold out and it's not very cold you might get another four months out of the battery but eventually it will begin to do this same scenario when it is warm because the chemical reaction between the plates in the battery has already drained most of the electricity out of the battery.
When batteries are cold, the chemical reaction which generates the electricity would you use to start your car is limited. As a result there's less starting power available for you when you were starting.
While oil viscosity does go up when it is cold, most engines now use 5W30 and there is less of an issue with that weight of oil unless it's below 0 Fahrenheit. Of course if you are due for an oil change that may help as there is less buildup of Gunk it within the oil as well.
The temperature of a cold engine also does cause vaporized fuel to condense on the cylinder walls which limits the amount of combustible fuel within the cylinder at the time of the spark. But that effect rapidly goes away once the engine is running and the cylinder walls begin to heat up.
A third issue for very old cars is that their compression due to wear on the cylinders and compression rings within the cylinders goes down also causing low energy production from the engine. Unless you absolutely totally abused this engine by not changing the oil ever. 3 years should not be enough to cause that kind of wear. However it is something seen in vehicles over 10 years old which were not not maintained properly.
It may also be prudent to check your charging circuit for your battery. You could heavily load your electrical system by turning on your high beams turning on your windshield wipers on full and turning on your heater and air conditioning full blast. And then see if your headlights flicker a little if you're running your engine. When you take your car into a auto parts store and have them check the battery and the charging system they will have you do that while they are monitoring the amount and quality of current put out by your alternator. If the engine has been running a while it may not be as noticeable a hit on the battery because the battery has been recharged. This is why some shops will have you leave the car overnight so they can do this test while the battery is cold.
