Have you measured the temperature of the IRLZ44's? At 3 amps, they should be dissipating less than 1/2 watt. The TO220 package has a Tja of 65 deg C/W so at 1/2 watt they should not be getting extremely hot, even without cooling. Also, with a Tjc of 1 deg C/W they can be run at case temperatures of 100 deg C with no problems, but at 1/2 watt, they shouldn't be getting that hot.
I suspect that you are not fully driving the gate to the required 4 volts above the source. The voltage out of a 74ls00 is typically only 3.5 volts, so it is too low by it self. You should at least be using CMOS to drive the gate, and probably a dedicated MOSFET driver. What value are your current sense resistors? Since you are running the sense voltage to the PIC without an amplifier, the voltage drop across the sense resistors is probably rather high. The source on the MOSFETS will be raised above ground by the voltage drop across the sense resistor, so this has to be subtracted from the 3.5 volts out of the 74ls00. You might be only getting 2 volts of drive to the gate. This would cause the IRLZ44's to get much hotter than necessary.
Here is one alternative to the current sense resistors. http://www.allegromicro.com/hall/currentsensor.asp