Are the orders of reactants with respect to a reaction different for different starting concentrations?
A reaction's rate does depend upon the consumption of its reactants, and the manner in which the reactants interact. Let's consider the following reaction: $$\ce{A + B -&gt; final products}$$ The rate of consumption of  reactants $$\dfrac{-d[A]}{dt}= k[A][B]$$ and $$\dfrac{-d[B]}{dt}= k[A][B]$$
It seems that this reaction is a second order reaction since the rate order appears to be:$$\text{Rate} = k[A][B] $$
As @Andrew astutely pointed out in the comments, a reaction can be of a lower order if one of the reactant's concentration is much higher than the other's.
Let's suppose, that one reactant is in great excess (say $10 \text{M of B vs } 0.01\text{M A}$)
So what we're observing now is that the reactant B is barely consumed, yet the reaction terminates since reactant A, the limiting reagent is exhausted.
In other words, the rate equation looks something like this: $$\text{Rate}=k'[A]$$, where $k^{'}=k[B]_o$ .Now, the reaction appears to be a first order reaction. This is known as a pseudo first-order reaction, since the rate of the reaction ultimately depends only on one reactant.
An example that I found here:
$$ \rm{CH_3Br + OH^- \rightarrow CH_3OH + Br^-}$$

[...]&quot;Imagine we had an initial concentration of CH3Br of 100 μM and and an initial concentration of OH- of 10 mM.   Now even if all of the CH3Br has reacted the concentration of OH- will be essentially unchanged.  Therefore during the course of the reaction, the concentration of OH- will be essentially constant.  This makes the reaction &quot;like a first order reaction&quot;, thus the name pseudo-first order.&quot;

Effectively, the rate now is: $$\ce{rate= k'[CH_3Br]}$$
This can also be mathematically represented in the integrated rate law:
$$\dfrac{1}{\ce{[OH-]_0 - [CH3Br]_0}}\ln \dfrac{\ce{[OH-][CH3Br]_0}}{\ce{[CH3Br][OH-]_0}} = kt \quad \ce{where [OH-]\neq[CH3Br]}$$
Now, since $\ce{[OH-]_0 \gg [CH3Br]_0}$, we can write the equation as:
$$\dfrac{1}{\ce{[OH-]_0 - [CH3Br]_0}}\ln \dfrac{\ce{[OH-][CH3Br]_0}}{\ce{[CH3Br][OH-]_0}} \approx \dfrac{1}{\ce{[OH-]}}\ln \dfrac{\ce{[CH3Br]_0}}{\ce{[CH3Br]}}=kt $$
Remember, however that the rate and order of a reaction usually depends upon its mechanism.
For further reading, check here and here as well.