I have found that any head gasket leak that causes the cooling system to pressurize too much will also leak coolant into that cylinder when the engine is off and cooling down. This causes a rough cold start as the coolant shorts out the spark plug briefly before it clears and begins running properly on four. If the cold start performance is OK, then I would say, especially as the heater works so well, that you have a blocked radiator.
Quick check for the rad. Remove both large hoses. Cover the lower outlet and fill the rad. Remove the cover (maybe your hand) from the lower outlet, and the water should run out smoothly and quickly. If it gurgles, or changes "velocity" as it runs out, you have some blockage in the core. Re-core it or replace it.