Во-первых, поправочка: скорость света одинакова в любой инерциальной системе отсчёта. Если система ускоренная, то скорость света может быть различной.
А что касается эффекта Доплера. Представьте себе световую волну как отдельно летящие шарики, расстояние между которыми равно длине волны. Если источник этих шариков будет от вас удаляться, то расстояние между шариками для вас увеличится. Если источник будет к вам приближаться, то наоброт - расстояние между шариками для вас уменьшится. Я пишу "для вас" имея в виду, что расстояние между шариками вы измеряете своей неподвижной линейкой. А то что скорость света будет постоянно лишь означает, что с увеличением длины волны будет падать частота света, и наоброт. Так и происходит в реальности.
Красное смещение - эффект сдвига длин волн в сторону их увеличения (или, что тоже самое, уменьшение частоты), а не скорости (!!!). Формулу для величины этого изменения при относительном движении источника и наблюдателя можно получить как раз из Специальной Теории Относительности. Так что никакого противоречия нет.
Сломай мозг: что такое частота? Не скорость ли колебаний, не? Даже по их размерности: 1Гц == сек^-1 == раз в секунду. :)