I rather doubt that he was choking. If you just started feeding pellets after switching from flakes, you might be seeing the simple difference in "chewing". Since goldfish don't have teeth or a stomach to soften food, they grind up food against bony plates in their jaw before it passes into their gut. Pellets cause much more vigorous grinding and you'll probably see big gill swishing and mouth movement.
If the pellets are smaller than the black part of his eye, they should be the right size. If in doubt, buy a smaller pellet.
As long as you're seeing evidence of the pellets in his poo, don't worry too much about it.