....and although I never lived in Virginia (I've lived in NC) I don't think it gets as cold as here in the winter. In fact, I'd place a large wager on it
I was just speaking comparatively, the diesels I've driven would start blowing heat within a minute or 2, my V8 pickup truck won't blow heat for about 10 minutes. The only exception I've seen is my Escape Hybrid. That will start blowing heat in about 30 seconds.
My friend's 1980 diesel Rabbit would leak heat from the floor vents all the time. Even though a diesel can burn less fuel, the higher compression ratio might aid in creating heat. So they could generate heat faster than a gasoline engine, when driven. TDIClub claims that the amount of fuel burned at idle will take forever to heat the engine to the point of heating the cabin.
Tiny engines, like the 0.8L in a smart diesel, have a higher surface area than larger engines. That with the smaller mass mean the engine will radiate heat faster than the big ones. The faster air cooling means the coolant takes longer to heat up.
Many hybrids use supplemental electric heaters to make up for the ICE running less to generate heat.
The basic problem is that internal combustion engined cars use waste engine heat to warm the cabin. As the engine becomes more efficient there is less waste heat. At idle, diesels still run full charges of outside cold air through themselves, and that cold air also cools the engine. Yes, the air is heated by compression, but it cools again during the ensuing expansion cycle. In the end, the only place the heat comes from is the burning of fuel. You don't burn much fuel, you don't get much heat. You want the engine to warm quickly, you start it, wait a short time (less than a minute) for the oil pressure to come up, then drive off. If circumstances permit, stand on the accelerator to get the turbo to spool up. If you worry about potential damage to the engine, examine the way in which a standby generator starts when the power fails.