I would vote for AoEII. Definitely one of the better MP games out there.
Warcraft III wasn't much my cup of tea for mp. I would much rather play AoE in multi-player.
Another game in the vein of those two is Age of Wonders Shadow Magic. Has an entertaining battle system. Trouble is in how the battle system works in mp.... everyone has to watch everyone else's battles. That has been a big gripe for me.
Never Played Lords of Magic in multi-player but it is enjoyable enough for a time in single player, so that one is a possibility.
Stars! is an interesting old game that is enjoyable in multiplayer. Lots of micromanagement options though. This means that games can go on for a LONG time if you got a 'perfect' player playing with you. Normally though I can finish a game in a couple hours.
Deadlock is another simple game that is enjoyable enough in MP[though I would rather play a game of Stars! anyday].