The order of the explanatory does not matter in logistic regression. The symptoms you describe, i.e. the unstable results, may hint at multicollinearity problems or problems of quasi-complete separation in your data. Do you also have large standard errors? As your independent variables are factors, you can tabulate them one against each other and inspect the relation between them. You should also tabulate the covariate patterns against your dependent variable. You can also start by fitting the model stepwise. Then you will see at which point the problem arises.
Let's think about regular linear regression, and to make it concrete, let's say we are trying to predict height of people. When you regress heights against just an intercept term and no predictors, the intercept term will be be the height averaged over all the people in your sample. Lets call this term $\beta_0^{\text{no predictor}}$
Now, we want to add a predictor for sex, so we create and indicator variable that takes a 0 when the sampled person is male and 1 when the person is a female. When we regress against this model, we will get an estimates for an intercept term, $\beta_0^{\text{male reference}}$ and coefficent of the sex variable $\beta_1^{\text{male reference}}$. The estimated intercept is no longer the average height of everybody, but the average height of males, the coefficient of the sex variable is the difference in the average height between males and females.
Consider if we decided to code our indicator variable differently, so that the sex variable took the value 0 if the person was a female and 1 if the person was a male, in this specification of the model we get the estimates of the intercept and coefficient $\beta_0^{\text{female reference}}, \beta_1^{\text{female reference}}$. Now $\beta_0^{\text{female reference}}$, the intercept term, is the average height of females, and the coefficient is the difference in average height between females and males. So
$$
\begin{align}
\beta_1^{\text{male reference}} &= -\beta_1^{\text{female reference}}\\
\beta_0^{\text{male reference}} + \beta_1^{\text{male reference}} &= \beta_0^{\text{female reference}}\\
\beta_0^{\text{female reference}} + \beta_1^{\text{female reference}} &= \beta_0^{\text{male reference}}
\end{align}
$$
So, by changing how we coded the indicator variable we changed both the value of the intercept term the coefficient term, and this is exactly what we should want. When we have a multivalue indicator, you will see the same kinds of changes as you specify difference reference levels, i.e. when the indicators take on the value of 0.
In the binary indicator case the p-value of the $\beta_1$ term should not change depending on how we code, but in the multivalue indicator case it will, because p-value is a function of the size of the effect, and the average differences between groups and a reference group will likely change dependent upon the reference group. For example, we have three groups, babies, teenagers, and adults, the average height difference between adults and teenagers will be smaller than between adults and babies, and so the p-value for the coefficient for the indicator of being an adult versus a teenager should be greater than an indicator of being an adult versus a baby.
Best Answer
Stepwise variable selection procedures without using penalized maximum likelihood estimation are invalid. Pre-specify your model or use data reduction (unsupervised learning) first. Much has been written about this. Stepwise variable selection is highly unstable even with nothing but beautiful continuous predictors, and it badly distorts statistical properties of the result.
There are no bad consequences of imbalance, just a fact of life that predictions for infrequent categories will have low precision/wide confidence intervals.
When thinking of imbalance, don't think about relative frequencies but rather use absolute frequencies. If you have 1000 subjects in a category, no matter how low a proportion of the whole that is, you have an excellent information base for making estimates.