As you probably know, before there was WoW there was a series of RTS games that established the Warcraft universe. The last of them, Warcraft III, had a big focus on "hero" characters (you controlled Thrall, Cairne, Sylvanas, Illidan, Kael'thas, Arthas, etc. at various points in the game). These characters were way more than standard RTS units, they had unique sets of abilities and could be revived at a special building when they were killed.
WC3 had a fantastic mod scene, with a lot of mods built around the idea of hero characters. One of these mods was "Defense of the Ancients" or DOTA. In DOTA each player takes control of one hero character; you can't build structures or other units, instead there are waves of "minion" units that spawn automatically and march toward the enemy base. The goal is to work together with your teammates (and minions) to destroy a series of defensive towers, to push toward the enemy base and finally destroy it. It's a PvP game, so the enemy team is of course trying to do the same thing to your base.
If you know the RTS terms "macro" and "micro," it's kind of like an RTS game where you only worry about microing your hero… combined with a double tower defense game… with role-playing elements. (You level up & gear up your hero on a per-game basis.)
DOTA basically spawned a whole new game genre, with the most direct successors being Heroes of Newerth (which has a reputation for hardcore-ness, probably not great for a first-timer), DOTA 2 (coming soon from Valve), and League of Legends.
At this point, you should download League of Legends RIGHT NOW -- it's free to play, really! -- and check it out yourself. It has a good tutorial system and you can play games against AI bots until you're comfortable enough for the PvP game.
Summoner's Rift is basically the "original" 5v5 DOTA map, this is what the purists play.
Twisted Treeline is a 3v3 map, it has the same goal of pushing towers and destroying the enemy nexus, but is much smaller and makes for shorter games.
Dominion is a brand new 5v5 map with a different objective, you need to capture and hold more towers than the enemy team (think Arathi Basin). It's a lot more active, you're constantly fighting and you don't have to worry quite so much about some of the genre's more arcane elements like feeding and last hitting.