I would say give Natural Swimmer and Water Breathing in the Water base heritage feat and give either Breathless or Flight in the Air base heritage feat.
The reasoning would be that neither Swimming nor Water Breathing are common, necessary or particularly useful. They're lifesavers only situationally. Flight, however, is almost universally useful. (More useful than when swimming isn't since you can fly over water as well as swim through it. Swim only wins underwater.) Breathless, likewise, has a superset of uses over Water Breathing. Anywhere you'd want to be Water Breathing you'd rather be Breathless. The only place you'd want to be Water Breathing or Breathless is, again, underwater.
So since the water abilities are rather useless and the air are overuseful, just give more water abilities. Earth could get a scaling Natural Armor. I don't think there should be a penalty to land speed regardless. I agree that Fire could get get a damage die increase, possibly scaling, and be balanced against Earth's ability.