I am a big fan of the basic four elementals: air, earth, fire and water. They are just beat sticks that pound PCs to the ground quite effectively. There is nothing but raw, brute, power in these creatures.
They may not have all the coolest bells and whistles that others - like the genies, but adding them to an encounter means the PCs have to worry about them.
And they scale throughout the PCs' own careers, from the small at low levels to the elders of higher levels.