Which town is easier to win with when playing against other players on Random maps?

You should definitely pick the hero Gurnisson for the Barbarians.

Or Grechkin ;). I personally enjoy playing as him because Gurn often arrives without a weapon. And Grechkin tears everyone apart with his goblins. Plus, it's easier to carry angels and wyverns with Pathfinder.

That is, the heroes are slow.

The lurkers look pretty good on greased goblins with a speed of 7.
I also like the Barbarians, but I agree that they usually have poor respawn points. But sometimes the generator will place a bunch of gnomes, which provides good experience and money.