^ The fan system has several inputs that determine the fan speed. AC being on only toggles one of those inputs. One comes from the fan thermo-switch that is next to the engine temperature sensor, one is associated with electrical load I think, and I think the other is controlled by whatever fan temperature is set on the ECU.

So if you have a bad relay or a wiring issue that is disrupting some of those fan triggers, your fans may still come on but never reach full speed.

Heater core blockage shouldn't heavily impact engine temperature. As others have said the heater core is on its own parallel loop.

Air in the system can also cause temperatures to run hot, but if its staying cool when the car is in motion and only creeping up when at idle or in traffic then that really points to something with the fans.