Lords of the Realm II and War! Age of Imperialism. The latter was well-reviewed but didn't sell well. It's a superb adaptation of the board game of the same name and has lots of in-game options. LotR II is a turn-based-RTS hybrid set in the middle ages.

Get Company of Heroes from Steam. Its a steal right now.

Space Empires 4. 4x in space doesn't get better. There's also Space Empires 5 but most players prefer 4. Very cheap on steam.

You could always try "Men of War"...
I heard good things about it. (WWII strategy game)

Or its predecessor - Soldiers: Heroes of WW2 (GoGed)
And what about Eufloria? (Just joking)

One more suggestion for Europa Universalis (with all 3 expansions : Napoleon's Ambition, In Nomine and Heir to the Throne).
If you think it is too easy, you can switch to the mod Magna Mundi, it changes the game that much they are going to release it as a stand alone game in one year or so.