I too had never really used Explorers, except to pillage from time to time. I played C3C for about 7 hours last night though and can really see myself using them now in what is really, a very different game than Civ3.
Since maps cannot be traded until much latter, land goes unsettled well into the middle ages now. Even if you have seen all of the coastal land, you won't have seen inland on large continent or pangea maps. As well, sending out teams of explorers will ensure that you can cut off narrow access points to land or simply section off land you want to settle for yourself.
I can really see this cutting down on map trading every turn, at least until all of the land is settled anyway.