The theoretical answer to the first question is that it should not matter, but you have proven it wrong.
If you right-click the left-most operator in the plan and select Properties, what does it say for "Reason for Early Termination of Statement Optimization". I would not be surprised that it says something about a timeout. That is, SQL Server did not find the time to evaluate all possible plans. It could be that it evaluates plans based on the order of the index_id, which follows the load order. And for this query, there is more than one index that is possible to use, and so it ends up with the bad one.
Another possibility is that the two plans in terms of estimated cost are very close, and therefore it is a tossup which one is chosen.
For further discussion, we would need to see the query and the two plans. You can upload them on www.pastetheplan.com
How to determine which index to create first in future if there have more indexes?
Trial and error.
But a better reaction to an event like this is: how can we improve the query/indexing, so that we always get a plan?