Things I've immediately noticed:
1. Outlines vs. no outlines - the Air character has no outlines while the Earth class and weapons used by both have one - I'm not sure if this is just how things "turned out" or a conscious decision to make the Air character feel a bit more "light". With the current looks, it feels like inconsistency to me, I'm sure it would work better with a non-black color for the outlines but I'd still decide on one consistent look - either everything has outlines or there's none.
2. Proportion - both characters have different proportion and it's a great tool for building character of the classes, their difference in looks and therefore their powers/behaviors, but it seems that both they relate differently to the environment which would be the same for both - like they were made with different scale in mind. As a start, I'd try to get their both head in similar/same size and then differ the size of the body. I think the Air character should feel delicate in contrast to the Earth one, and currently, I think the Air class is more imposing.
3. Style clash - the Air class with more cartoony head, and height of ~3,5 heads clashes a bit with the Earth character which feels a lot more serious in proportion and style. The difference in shading is pretty significant, and the shading in the Earth guy gives a lot better sense of the his form, while the Air one is very gradienty. I understand you wanted the give him a more aetheric feel, but I think you should find the middle ground - don't use straight gradients, but don't define the forms as much as you would with a character made out of rock.
4. Weapons looks VERY generic - pretty run of the mill human guns, something that would work in war/soldier game - the idea of a War of the Elements, as you called it, gives GREAT potential - there's plenty of room to let your imagination gone wild.
Simplest thing you can do, is to take any of the known, established weapon types like guns, swords etc. and think of creative designs for them - Air class weapons could be made of very light metal, have a lot of curves, a generally "fluid" appearance while Earth's weapons would be crude and angular, made to be used by big, rocky hands
5. Colourwise you could use some hue shifts to escape the "colouring book" approach - the air is cyan, rock is brown etc. - vary the hue of your shades as they go lighter/darker, tint them.
6. You could work on the anatomy a bit, but I'm sure there's somebody out the who can give you a better advice in this matter than I can
I like the idea you have, I think it has some potential, but I recommend you do some more concept artwork (preferably, NOT pixel art) before doing any more actual game art - try to think about the environment and the setting of the game and then put your characters in. The current sprites, seem like both are from a different universe and that's the main problem IMO.