Starcraft (the first one without expansion) is really a no brainer here. It plays just like Dune 2 and the graphics are pretty much similar too.
I never liked Age of Empire because of those stupid reconversion priests. That really broke game play in that game and I have never seen an improvement in the sequels so I stopped even trying the newest games altogether.
Warcraft III is a more modern game but unfortunately quite failed in its concept. It is a RTS which heavily pick from some specific RPG elements. More specifically, heroes levelling. This mean that you can go nowhere without heroes (at least in the med to late game after they level) and that the whole game is centered on them and not on outpost or unit building like a normal RTS. That quite killed my interest for it, I have never completed more than a handfull of the second chapter missions because the story was so bland too. Take Warcraft I, make it play the hell of a lot faster, add heroes and voila! You got Warcraft III.
Two games I can very strongly recommend is Starcraft (original) and C&C (the original also). Another more modern game I could recommend for the RTS genre is Original War, especially if you like oldschool retro themes as you travel in time in this game and the Russian campaign take you further back in theme than reality.
Actually, out of the three games I just recommended here Original War is probably the one which plays the most like Dune II.