Some of your questions overlap so I’m not going to answer in the framework of 1 followed by 2, .....
An IIR filter ‘s stability is related to the location of its poles. If the region of convergence contains the unit circle, the filter is stable. This definition covers both causal and anti causal filters, so you can have a stable causal filter and an unstable anti causal filter or vice versa.
Filters are implemented in terms of their coefficients so you need to root the denominator polynomial to find the poles and this is an ill conditioned problem.
see https://math.stackexchange.com/questions/70015/roots-of-bivariate-polynomials
for an example. small perturbations in filter coefficients, like finite precision, can move the poles so that the region of convergence no longer contains the unit circle.
A good DSP book like Oppenhiem and Schaefer will discus work arounds like factorizing a polynomial into smaller stable polynomials and filter structures that are more robust to precision errors.
There are a number of functions in MATLAB that estimate oder for a given filter performance but these aren’t always reliable.
Ultimately one uses trial and error when designing a filter. start with an oder and test the filter. if the filter meets spec, stop. if not, increase order by one and repeat.
How do you know if a filter is stable? you test it, which is what MATLAB is good at, although add ons like the fixed precision tool box might make things easier.
Overdetermined filters can be stable or unstable. An overdetermined filter can be a poor use of computation.
FIR filters are always stable. While an IIR filter requires fewer arithmetic operations than a FIR filter, some processors have execution pipelines that penalize recursion, so you can be doing more arithmetic faster with a FIR filter than the equivalent IIR filter.
A FIR filter can be linear phase, which can be desirable in many applications. An IIR filter can only be linear phase over a portion of bandwidth.
IIR filters can borrow from analog filters lke the Butterworth filter you mentioned
The answer to question 3 depends on what you mean by best. It isn’t really an issue of order but how oder is structured