You weren't sure how to describe this problem, but your guess was perfect. Apple calls the disappearing icon animation the "poof" effect!
Even if you don't know which icon you removed from the Dock, don't worry about it. You can pick whatever selection of applications you want, from your Applications folder, and drag their icons into the Dock. If you pick a lot of them, your Dock icons all get smaller, but that's the only downside. If you don't use a particular application very often, you probably don't need its icon in the Dock, so "poof" it.