Both acid and calcium firm up pectins in vegetables like potatoes. A tablespoon of distilled vinegar/lemon juice when boiling the potatoes will leave them firm.
Another thing to try, to get the potatoes firmer, is to boil until not quite done then turn off the heat and let sit in the water until just right. It slows down the final cooking phase and makes it much easier to get them just the way you’d like. Give it a try!
Starting with the right potatoes. Around here they come in waxy (suitable for boiling and salads) and floury (best for roasting and chipping). Boiling them whole helps reduce the amount of water they absorb which can help them stay more firm too.
If you live in the States, what is sold simply as “red potatoes” in any supermarkets will be a good potato for this type of use. Anywhere where you want the potatoes to hold their shape (like in a stew or a salad), that’s a good choice.
(Link to 1940’s video featuring triplets singing a song with that name and doing some pretty amazing contortionist moves - featured here on the SDMB a few times…)
Agree with red potatoes; russets can get too soggy too easily. I usually cut mine up to the appropriate bite-size and then steam them rather than boil them. Yukons might also be a good choice.
You have to start with cold water. If you put very hot water in the pot with the potatoes and then boil them, the outside gets cooked before the inside. Then the outside is mushy by the time the inside is done. Use a sharp knife to check for doneness, when the knife will just go in with a little pressure, they’re done.
Also, make sure you’re using a thin skinned boiling potato. Reds are the best.