I love 4X games (Master of Magic being one of my all-time favorites), but I don't like the "traditional" RTS games like Warcraft or Age of Empires that grew out of the 4X genre - the ones where you harvest resources to build lumber mills so you can start training archers and so on. The reason I don't like them is that it just feels like a big mess with too much going on for me to reasonably deal with. The exception is Total Annihilation, which I like for its stripped-down management aspects and actually-pretty-cool combat engagements. I did play a lot of Warcraft 2 back in the day, but I probably won't ever play it again (it hasn't really aged well, anyway).
I was going through my game collection and found the Myth Total Codex, which I bought used a few years ago (back when EB Games still sold used PC games) but never played, so I installed it last night. It's taking a bit for me to get into it, and I'm terrible at it so far, but it seems worth sticking with. I like the idea of replacing unit spam and building hierarchies with formations, tactical planning, and using the terrain to my advantage.
I pretty much immediately ignore anything described as a real-time strategy game, because I expect it to be a Starcraft clone (the only reason I picked up Myth in the first place is because I already knew otherwise). Are there any solid RTS games (new or old) that I might have overlooked that don't follow that formula?
I do have Sacrifice from GOG, which I enjoyed.
Fallout Tactics I don't really care for. I've tried to get into it a few times since its release, but I just never liked it. I do own it, though, so I might give it another chance someday.

I dunno, Demigod?

Dawn of War 2

Yep, as already mentioned, Warhammer 40000 Dawn Of War 2.
I really enjoyed it and no base building. Great strategy game.

I don't think you can really place that in the rts category.
You might want to see if you can find
-The Gladiators: Galactic Circus Games-
Very hard, no base building. Probably hard to find though..
EDIT: I'm not sure about this, but I believe Hostile Waters: Antaeus Rising has no base-building?

Demigod is an example of what I might call an action RTS, as your base lives/dies depending on how aggressively you take down your opponents base. The only building that goes on is occasional upgrades as you get the gold to do so.
If you haven't played them, try the Dawn of War series (I haven't played DoW2, not sure about it: it requires Steam). There is base building, but not the traditional resources that you mine. Instead, you build generators and you can build units based on your requisition income. You get faster infusions of this based on how many points you hold during the levels.
Try the demo for Dark Crusade, it's pretty awesome.
Another one I've spent a little time on is Perimeter. It puts a neat spin on things, and there is also a demo for it.

Hostile Waters. Search this forum for my Let's Play thread, you might like it.

There' s Magic and Mayhem.

You may try ground control and ground control 2

Well what are you waiting for, give it a spin. ;) You can play all of the races (up to that point) on SP campaigns/skirmishes, and just the two races introduced in that Exp for multi-player.

You can try World in Conflict too.

Absolutely; i only played the 1st one, but i think GC 2 works in the same way: no base management whatsoever, new units comes as reinforcements, in waves, during the missions.
Great game
edit: Last but not least, Ground Control was released as freeware: [url=]http://www.fileplanet.com/promotions/groundcontrol/[/url]

World in Conflict is a good one.
The Kohan series have very streamlined building - such that it never gets in the way of anything; it's almost as if it wasn't there. Highly recommended.
The Total War series might be an idea.
If you like 4X space games, you might want to try Sword of the Stars Ultimate. Planet building is almost completely streamlined, and the strategic layer is turn-based, so you have plenty of time to think. Combat is real time and quite tactical, which is very good. It's my favorate space-based 4X game.