I worked backwards from Starcraft, and to my mind WC2 still feels a bit archaic, insofar as the two races feel nearly identical. WC3 did a better job of differentiating the Human and Orc units, and then of course added Dark Elves and the Undead to the mix, too.
But I will say that WC2 is the last major RTS I can think of with naval combat. After Starcraft streamlined it to be land and air only, it seems the entire industry followed suit. Even WC3 didn't bother bringing ships back, to my memory.
I remember being bummed when I played WC3 and there was no oil resource. Lots of sky and ground units, but I guess a navy just wasn't useful enough? Which I suppose I could see. A big benefit in militaries is the ability to quickly project power (from a carrier) or provide tons of logistics - supplies, blockades, etc.
These just aren't considerations in RTS games - they move too fast and the maps are too small. There really isn't a benefit to having a ship with all your planes just outside of the enemy's range - they could sneak attack you, and sending units from your own base really just isn't that much farther.
It's a shame to me that this isn't a more popular genre these days. It's easily my favorite.
C&C RA (1996) and RA2 (2000) both had significant naval units. RA3 (2008) went.. maybe a little overboard with naval units as well. That said, all other C&C games (Tiberium and Generals) both avoided naval units.
Try 'Beyond All Reason', a passionate FOSS recreation of the core of Total Annihilation.
It's got really decent naval combat, with a distinct feel compared to the land and air.
Age of empires always had naval combat. Supreme commander too. There’s a bunch.