In classical mechanics, specifying the initial coordinates and velocities of all particles uniquely determines the system's future ...
Uniqueness and existence are not guaranteed in classical mechanics. Physicists gloss over the cases where uniqueness is not guaranteed. Initial positions and velocities suffice if the resultant accelerations are Lipschitz continuous. The classical universe does not necessarily obey the Lipschitz condition.
One issue is that classical mechanics ultimately deals with point masses, and their use can result in infinities (which obviously violate the Lipschitz condition). The hand wave solution to this issue is that point masses don't really exist; they're just a nice mathematical construct. The mathematical singularities that can result from the use of point masses never actually occur in physical reality.
Another issue is that one can construct a Lagrangian landscape that violates Lipschitz continuity. Norton's dome (discussed here at physics SE) is a nice example of how violations of Lipschitz continuity lead to non-uniqueness. The hand wave solution to this issue is that the cuspy nature of Norton's dome represents something that doesn't exist in physical reality. Nature abhors singularities.
... we do not need to specify accelerations or higher derivatives.
This is a separate question, one that has already been answered nicely in the questions "Why are there only derivatives to the first order in the Lagrangian" and "Why are differential equations for fields in physics of order two."