Potatoes for potato salad work best when you add them to cold water and bring both the water and the potatoes to a boil on the stove together. This will give you the best results for a soft potato.  If you add potatoes to already boiling water, the starch reacts with the hot water and can make for grainy potatoes.