Played RTS since i had a PC, well pretty much anyway....... did play 6 years within an RTS clan, mainly playing the AOE series of games, also played a lot of C&C and various other RTS games.
So firstly CoH..... what a great game.... until after a few weeks of play then its just dull and restrictive....... lacking any variation of units when you compare to the other offerings on the market.
C&C have always been great games, especially fun for lan, too competitive online (i played my share

)
Now AOE, or the series, are great, simple, fun, and enough variety.... geez my mum plays AOM, and use to play AOE:ROR..... its a lovable game. I still play AOM, which imo (notice the IMO here) is still more fun then AOE3.
I've played them all, or most of them, WC3 + exp, Cossacks, Stracraft, C&C........ blah blah blah......could go on. but zzzzZZZZ i'd be bored just typing it.
For someone starting out...... AOE.... well anyone of the series, or settlers which is very alike are great easy to play games to start with, C&C would work great to if you prefer tanks and planes to knights and archers.... etc..