There is also a Trans fuse in the underhood fuse panel which I also tested and it was good. However, this fuse panel cover was missing on this car when I bought it so I am going to pull the fuse and make sure the contacts are clean. The engine compartment was pretty dirty so I will probably pull all the fuses and relays and clean the connections. According to a fuse diagram which I also just found on the internet, fuse #4 - the TRANS fuse - controls the 1-2 shift solenoid valve 2-3 shift solenoid valve, and Torque Converter Clutch Pulse width modulation solenoid valve.
Don't mean to rant, just thinking out loud. Once again, I will let you know what I find out on both issues (brake lights and trans)

Thanks for letting us know how it is going.

Many cars will not allow cruise control until they voltage that also goes to the brake lights . . . which is theoretically required in order to shift out of Park for the first time.

Right, from what I read the brake pedal sensor also controls the brake shift interlock system which, if not functioning would not allow you to shift out of park. I need to do some more investigating.

I had a the brake light switch fail on one of my cars. It started with suddenly not requiring pushing the brake pedal to shift out of Park for a couple of years, then it stopped turning on the brake lights. This switch has two circuits attached, one for brake lights and one for the interlock.

I think your Malibu does not require you to press the brake pedal to shift out of park at the first click before the ignition lights up. If true, that means that the interlock is enabled when by a circuit powering on with the ignition.

Okay, had a dumb a** attack. The key has to be on for the brake lights to work, since they are powered by the BCM which simply receives a signal from the "switch." Just for diagnostic purposes, the white wire is the 5 volt reference and should show 5V even with the key off like mine did. The brake switch or more accurately brake pedal position sensor, sends a signal back to the BCM when the pedal is depressed, then the BCM powers up the brake lights. So my brake lights worked once I reconnected the brake pedal switch and turned the key on but at first the 3rd brake light did not come on. I removed it, unplugged it and tested the wires for positive and ground which were both okay and then plugged the light back in and it worked. Still do not have cruise control, so I think it is either the switch or cruise control module, but I'm not worried about that right now. While testing fuses and cleaning the dirt out of the underhood fuse block which has been exposed with no cover for who knows how long, I removed the brake diagnostic resistor from pos #46 and found that someone had twisted a strand of copper wire around the terminals, effectively bypassing the resistor function. I removed the wire and tested the resistor and found it to show R of 62 ohms and put it back in. It did not seem to have any affect on the brake lights, I am not sure why someone would have wanted to bypass it. I also removed the TRANS fuse #4 and tested it with an ohm meter and cleaned it and sprayed the terminals in the fuse block with electrical cleaner.

As far as the brake pedal sensor controlling the transmission, from what I have read, its main function is to tell the TCM to disengage the torque converter clutch while braking. After doing the above things, I drove the car again. The 1-2 lag did not seem as bad, and the 3-4 was barely noticeable. I also cleared the codes before driving but the brake switch code came back although the check engine light has never illuminated while driving. Yesterday, I disconnected the battery to let everything power down. Today I will drive it again and see if I get any codes back.
BTW, the brake pedal does have to be depressed to move the gear shift out of park, I believe the brake pedal sensor also sends a signal to the BCM letting it know so that you can't put the car into gear with your foot off the brake aka "brake shift interlock system". I also found out that the fuse marked PEDAL in the interior fuse block is for the automatic adjusting pedal option. I found a good fuse block detail page that describes what each fuse controls.

A good scan tool will show the status of the switches. Look in the BCM.

Maybe I am grabbing at straws here, but I am beginning to think it might be an engine issue rather than a trans issue. While driving today, I noticed a sharp drop in the spark advance on my scan tool that coincided with the 'lag' I feel on the 1-2 shift. It takes about a half second for the scan tool to display it, but it is consistent and happens every time. The spark advance will drop to around 15 - I saw it go as low as 10. Once it jumps back up to where it was, then I feel the hard shift into 2nd gear and off it goes. I previously watched the TPS sensor and it appears to be working normally with no 'dead spots.' I am going to try it again and watch just the TPS and spark advance and see if there is any correlation.
In the meantime I would welcome suggestions what to look for to stop this drop in spark advance. Could it be a crank or cam position sensor? My scan tool doesn't read these I don't think, I haven't noticed them on the list using Live Data.
After driving it again today, there were no codes set, and the check engine light has never come on.

Should also add, I replaced the air filter already as a general maintenance precaution. I don't think this car has a replaceable fuel filter, I find none listed in parts suppliers. I don't think it is a fuel issue as it starts easily and runs great, lots of power and torque, it will squawk the tires in drive from a dead start.

I believe this is part of what the PCM does to smooth the 1-2 shift without the transmission being one of the newer torque-managed designs.

. . . and perhaps if the transmission has already done it'* PWM routine and thinks it has shifted (but hasn't quite gotten done with it) this would be the result.

Do this with the engine stopped. Move pedal very slowly and see if it ever jumps along the way. Test going down and up.

Fuel consumption is highest at the top of any gear at wide open throttle. This is when fuel demand is highest.