For Genre, I think another FPS could be done really well. Either a Battlefield style one, or a squad based shooter. Something with a larger scale than 16v16 cap.
For storyline, I would prefer Tiberium. After Red Alert 2, I lost interest due to the overcamping. RA1 had some serious dark tones to it, and felt serious. RA2 traded that for jokes.
For mechanics, my favorite RTS is Emperor Battle For Dune, with powerful infantry, in depth unit tactics, and completely different factions. More explanation and detail later.