Awesomeness: If air units had dogfights instead of staring at each other a firing missiles.
Zerg Upgrade: Tunneling, Post-Hive Technology allows movement underground.
I say medics should stay the way they are...
Cool Idea: Since the High and Dark Templat have opposing energy forces, merging them could be the Toss Super Weapon, since only they lack one... Say you're fighting a losing battle, combine a DT and HT and watch the fireworks

. A cool explosion, like a Plasma Grenade going off...
Terrans have nukes, Zerg have Infested Terrans, here is the Protoss answer...
Terran players can upgrade weapons for marines, say research medical equipment and then specify that's what the marine will be equiped with. The Marines, Firebats, and Medics could be combined, but in addition have, say, snipers. Heavy damage to infantry units, little damage to mechanized or large units, slow cooldown. Shotgun Marines, close range unit (closer than marine but farther than firebat) that does massive damage to small units but (once again) very little to large ones.
Marines could be equipped with grenades to spice up combat. In turn, Zealots could have, like, their own breed of grenade and Zerglings could have toxic spores. They run out but could be resupplied at Depots, Gateways, and Spawning Pools.
More interesting combat, random stuff like accuracy and fear that hinders their efficiency. <<< The zerg could have an advantage because in the face of overwhelming numbers, they still lack fear.