My favourite strategy games other than Civ include the following:
Command and Conquer Tiberium Dawn and Sun plus Red Alert (I and II): excellent fun and overview!

Love the music and Kane is a excellent villain. Dawn continued the glory of Dune II, Red Alert set a new standard for PC games, Sun had some interesting environment mechanics (plus base gates!

) and RA II was as funny as Hell.
Heroes of Might and Magic 2-4: number 1 was among my first ever games but it improved greatly in 2 and 3 carried to a new marvel. 4 is controversial but I like it!

The game series has a excellent flow and music is grand. I also like the whole themes set to have a grander to it.
WarCraft II-III: good world and number 3 had excellent factions!

The RPG mechanics of 3 also made map editor could have fun; fancy Diablo using WarCraft as your setting? Use the map editor!

Also great music.
Total Annihilation: "brilliant" would be a understatement. Music is a legend on itself, army scales are amazing, the "gun vs. gun" aspect forces focus on tactical consideration and basically a grand game.
StarCraft: I have not played II (yet) but the legend be noted.
Dungeon Keeper 1-2: funny as Hell (no pun attended

) and excellent strategic notions. Play if you fancy to try out a British classic.
Crusader Kings 2: peril to thee who notices the hours I spend on this game! Deep character interaction, a not too complex mechanic. See the fun of making the Sultanate of Ireland, observing the Aztecs taking Rome (viva la alterative history DLC), dominating the Mongols as Venice or demonstrating the glories of the Norse by reforming the faith and taking over Europe with your raids!
Alpha Centauri: ok this is cheating since its basically "Civilization IN ANOTHER WORLD!" but this is forgiven by the political depth, ecological mechanics and the whole "design your own units" thing. Also it is as quotable as chocolate be delicious.
XCOM: UFO Defender and XCOM: Enemy Unknown: defend humanity from a coalition of colourful (and scary, especially with the chrysallids) invaders. The music is awesome and the research is great!

The original has excellent base deployment, while the reimagining keeps up with the energy, worthy of sitting on the XCOM throne.
Age of Empire 2 and Mythology: 1 is awesome (especially with music) but 2 is WOW! Excellent unit sets and epic campaigns. Age of Mythology meanwhile does a great notion in making the 3 powers special in their own ways.
Dwarf Fortress: although its complexity may cause issue in getting use to this game the possibilities from it is grand. Enjoy the exploration, create/dig a great fortress, defend yourself against goblins, hate elves, fear undead fish and prepare to embrace the term "LOSING IS FUN!" for that is the way this game goes! There is also a rouge mode, allowing you to explore your fortresses as a adventurer!
Then are the additional high places:
The Pikmin series: not a traditional strategy series but it manages to bring a strategy to consoles while fitting with consoles. Also I like exploration!

The game series has great music. I have only played the start of 1 and not tried 2 but these games deserve the high praise they earn. 3 is great, especially with the tasking element.
Little King's Story: take Pikmin, place in a Medieval setting, centre in a colourful town, have your aim be taking over the world; that be this game!

The music composes of remixed classical music and the characters are humouring.
Evil Genius: Dungeon Keeper WITH BOND SUPER VILLAINS! Enjoy the fun of a mission to shrink and steal the Eifel Tower, while combating lowly investigators to super agents with traps and minions, including henchmen. The game suffers in replay value (you will have a total of 2 isles, not counting the tutorial) and the game can be very easy late game (even on hard) but it is fun to take over the world!
Galactic Civilization II: the customising nature of the game (especially with ships) is notable along with a advance A.I. that loves to plot. The game suffers in the music department but it is fun.
Startopia: a British classic that sees you oversee a space station. Provide tourists with joy, care for the health of the ill, defend against hostility, manage the environment of the top deck to garden results, enjoy the catchy music and lol as much as possible to the game's humour.
MechCommander 1-2: set in the BattleTech universe you command a squad of mechs against other mechs.
Syndicate: more a real time tactics game but enjoy commanding your cyborg agents in this cyberpunk setting against others who want to proclaim themselves the title of "the Man." Dominate the world: violent corporate warfare style!

Syndicate 2 is good too....but do forsake the "sequel" EA released recently.
Europa Universalise 3-4: while not as accessible as Crusader Kings 2 the depths of these games are legendry. Enjoy the music, the possibility of making small nations dominate the world and learn to embrace France as the final boss she truly is!
Master of Magic: play as a wizard in a civ like game! Research is set to spells while you get to explore two worlds! Limited in diplomacy however with the 2 victory conditions disallowing the possibility of a peaceful game. Still a great classic.
Earth 2150: the Earth is going to die! Humanity must flee... by the three large factions fighting each other to see who gets to launch their ship! Enjoy customising units, good music, good environment and the joy of the Lunar Corporation's weather control device in how it truly masters the control of the weather.
The Battle for Wesnoth: a open source tactical game with diverse powers and good music.
StarWars: Empire at War: the space combat is the thing most recommended here, especially with the fun of ordering your rebel forces to bring down a star destroyer or go on a planet killing rampage with the Death Star. Did I mention you can command the Emperor in land combat while the AT-AT proves itself boss with its UNLIMITED STORMTROOPERS or command what are basically mammoth tanks as the rebels while rocketing down those AT-STs?
Tropico 4: can I count simulations as strategy? If so enjoy ruling a Caribbean isle in this Cold War black comedy!

Alas I have only played number 4.
Emperor: Battle for Dune: the only game based on Dune I played. Excellent music and good faction notions.
Ok... technically I have been listing strategy games I played but these games are awesome.