Why does starting up while cold make a laptop run slowly until I restart it after it's warmed up?

The slowdown is caused due to the processor clocking down during boot-up to prevent overheating damage. Paradoxically, laptop CPUs are likely to overheat when booted at cold temperature due to the nature of the cooling assembly used in laptops.

Laptop CPU cooling assemblies usually consist of a flat plate positioned over the CPU and connected by a long copper heatpipe to a heatsink and fan off on the side of the case. Heatpipes contain liquid in a vacuum which provides cooling by capturing heat at the CPU end through vaporization and releasing it at the heatsink end through condensation. It is very likely that in cold temperature, the liquid within the heatpipe freezes and it no longer functions effectively for cooling the CPU until thawed. According to Wikipedia:

Below a certain temperature, the working fluid will not undergo phase change, and the thermal conductivity will be reduced to that of the solid metal casing. One of the key criteria for the selection of a working fluid is the desired operational temperature range of the application. The lower temperature limit typically occurs a few degrees above the freezing point of the working fluid.

This would not happen in a desktop since the heatsink is in actual contact with the CPU and can thus absorb and dissipate heat in and of itself. However in laptops where the heatpipe critical for funnelling heat to the heatsink, it is quite possible for the CPU to overheat and become throttled while the heatpipe is warming to operational temperature.

Virtually all electrical items have an operating temperature range. It's not just the battery that could be affected, but the other resistors and capacitors etc. on the motherboard.

The whole laptop will need to be kept within this temperature range.

I'd go with the insulated bag idea and also leave it to warm up for a few minutes (next to a radiator perhaps) before turning it on.

Just a guess: Perhaps when the machine starts and the battery is cold it has little power output and therefore the machine enters a power saving mode.

Could you try keeping the battery inside overnight and starting the cold computer with a warm battery?