Wine appdb says AoE 1 and 2 should work rather well, but AoE 3 won't likely run yet.
I don't know much about Linux native RTS games. So far no one has poked me to say here's an awesome RTS for Linux.
But here's a list.
Actually, I've heard people say good things about Spring. It's like Total Annihilation.