I suddenly have an urge to play rts games again seeing as they never bore me. I have played the whole Age of Empire series including Mythology. (AoE 2/3 ftw) I also have Rise of Nation + the expansion. I even have Warcraft 3: Frozen Throne. I have been playing all of these for so long now I want to change to try something new.

Can anyone recommend some RTS games that has heroes with spells. (Like Warcraft 3.) Don't say Warcraft 3 because I already have it. The regular game combat in warcraft 3 doesn't interest me. I only play it for custom maps on BNet. ^^

Last request: I remember I tried a demo of this one RTS. The heroes actually had a skill tree and each skills can go up to a few levels such as 10. You can also rotate your army in the direction you want them to look. Anyone know the name of this game? I want to give it another try. Last time I tried it, my computer was really bad so it lagged.

EDIT: I found out the rts with heroes that has a skill tree is called Warhammer: Mark of Chaos and the expansion Battle March (Not part of the 40k series) which is coming to xbox and PC this December. Turns out that you don't build stuff like DoW. It's just armies clashing armies. I heard it wasn't that good though... Still, it sounds fun to me.