Children should first visit the dentist on their first birthday or within six months of the child's eruption of their first tooth, whichever occurs first.