Usually there are just three or four of these on the entire map. Depending what sort of game you're playing, you might go for it, or you might not. If I find my starting position is on a smaller island, I end up producing galleys and once I've moved a settler or two to adjacent land, then I start the search for the artifacts. If my starting position is already excellent, or if I have neighbors that are uncomfortably close, I may not put as high a priority on looking for artifacts (which more often than not are located on hard to reach islands). As for Atlantis, this is indeed one of the best artifacts, but it's also found only in deep water, meaning you can't just stumble across it until later in the game.
This was one of Sid's early design ideas, and has grown to become a favorite around the office. It's another choice a player has to make early on in the game, and a variable you have to take into account. It's always disconcerting when your advisory pops up to tell you that your aggressive neighbor found the Knights Templar.