I don't want to clutter the thread with too many posts, but based on some of the solutions, they suggested replacing the coolant temperature sensor and / or the wiring harness to the PTC heater. I'll update this post with some of the information I found, as I am going to try and solve this myself as well.
Coolant Temperature Sensor
They said the Nissan part number is #226303NA0A. You can typically buy parts here in Canada (and the US) from Rock Auto or on eBay. When I looked up 2013 Nissan Leaf, there were none in stock. These temperature sensors do not seem to be that unique. When searching eBay, sellers also indicated these part numbers:
J10 JJ10 B17 B10 S14 N15 K13 Z51 C11 B16 R51 L31 F15 N50 J11, T32 EZ0/1 L30 L70 BZ0 BJ0 JK0/1 BR0/1 CR0/1 HY B9A/M K9A/M, HR16DE QG16DE SR20DET SR20DE HR12DDR YD25DDTi MR18DE MR20DE, VQ40DE VK56DE VQ35DE MR16DDT MR20DD M4R 711 M4R 713 K4M 838, M4R 714 M4R 751 H4M 729 M4R 746 2ZV 604 K4M 866 K4M 858 V4Y 701, V4Y 711 V4Y 715 M4R 700 M4R 701 2TR 702 2TR 700 2TR 703 M5M 450, M5M 400 H4M 438 H4M 738 H4M 430 H4M 730 H4M 740 BLUE PRINT, ADN17204 ADN17205 BOSCH 0280130071 0280130072 0280130081, 0280130082 CALORSTAT BY VERNET WS3001 DACIA 2263044B20, 2345012920 DAIHATSU 226300M200 DELPHI TS1024812B1 EBERSPACHER, 9003703 ERA 330759 FACET 73225 HELLA 6PT009107531, HERTH+BUSS ELPARTS J5621011 HONGQI INFINITI A178352A, 226301W400 2263043Y00 2263044B10 2263071L00 226307Y000, 2263095F0B 2263099B10 22630ED000 22630JN00A JAGUAR METZGER, 0905129 NISSAN 2263000QAH 2263001U00 226303NA0A 2263044B00, 2263099B00 22630D9702 RENAULT RENAULT TRUCKS SAMSUNG VEMO, V38720004
Searching for Nissan's 226301W400 / 2263000QAH / 2263099B00 seemed to come up with the same "FACET 73225" also listed above. Price as of 2019/10/01 is $13 Canadian.
Here's a local thread on how to replace it:
viewtopic.php?t=25000
After receiving the new part, it looks like the probe is slightly larger than the OEM one, but the Facet 73225 fits perfectly. It comes with a metal washer instead of the rubber one, so I believe it's important to swap to keep the rubber one. After replacing it, turning on the heat to max and fan to max doesn't seem to engage the PTC heater on mine. On to the next option...
Heater Harness
These may or may not be the right harness for the heater. Keeping them here as a record of what I found at NissanPartsDeal.com :
Harness-Sub, Blower Unit
27020Y Nissan Leaf S 27206-3NF0A (Listed at $26 USD as of 2019/10/01)
27020Y Nissan Leaf SL/SV 27206-3NF2A (Listed at $26 USD as of 2019/10/01)
27020YA Nissan Leaf Harness-Sub, Blower Unit 27206-3NF1A (Listed at $20 USD as of 2019/10/01)
Heater Assy-PTC
27143N 27143-3NF1A Replaced by: 27143-3NF1B (Listed at $600 USD as of 2019/10/01).