Linear stability of horizontal and inclined stratified channel flows of Newtonian/non-Newtonian shear-thinning fluids is investigated with respect to all wavelength perturbations. The Carreau model has been chosen for the modeling of the rheology of a shear-thinning fluid, owing to its capability to describe properly the constant viscosity limits (Newtonian behavior) at low and high shear rates. The results are presented in the form of stability boundaries on flow pattern maps (with the phases superficial velocities as coordinates) for several practically important gas-liquid and liquid-liquid systems. The stability maps are accompanied by spatial profiles of the critical perturbations, along with the distributions of the effective and tangent viscosities in the non-Newtonian layer, to show the influence of the complex rheological behavior of shear-thinning liquids on the mechanisms responsible for triggering instability. Due to the complexity of the considered problem, a working methodology is proposed to alleviate the search for the stability boundary. Implementation of the proposed methodology helps to reveal that in many cases the investigation of the simpler Newtonian problem is sufficient for the prediction of the exact (non-Newtonian) stability boundary of smooth stratified flow (i.e., in case of horizontal gas-liquid flow). Therefore, the knowledge gained from the stability analysis of Newtonian fluids is applicable to those (usually highly viscous) non-Newtonian systems. Since the stability of stratified flow involving highly viscous Newtonian liquids has not been researched in the literature, interesting findings on the viscosity effects are also obtained.