The secret to the best potatoes in potato salad is to cook the potatoes as whole as possible. The more you chop the potatoes, the more water it absorbs. You want to avoid that when making potato salad. Try to look for evenly sized potatoes. If you have potatoes that are larger, just cut them enough to be about the same size so that they cook evenly. You also always want to start the potatoes in cold water. Bring the potatoes and water to a boil and let them cook just until they are fork-tender. You do NOT want them to fall apart.