Это сочетание не тавтологичное (тавтология – неоправданное соседство однокоренных слов, например: следует отметить следующие особенности), но плеонастичное (т. е. лексически избыточное), ведь ступня – это и есть нижняя часть ноги.

Нет, это корректное сочетание, оно зафиксировано словарями русского языка (см., например: Большой академический словарь русского языка. Т. 7. М., СПб., 2007).

Это тавтологичное сочетание, но не ошибочное. Тавтологию здесь можно рассматривать как стилистический прием, позволяющий акцентировать то понятие, которое заключено в корневой части повторяющихся слов.

Формально сочетание можно отнести к тавтологичным: в обоих словах есть корень -став-. Однако ошибочным оно не является. Родственность слов представьте и выставка не очевидна, и даже при определенном подходе к морфемному членению корень -став- в первом слове может не выделяться. Например, в «Морфемно-орфографическом словаре» А. Н. Тихонова показан корень представ-. Созвучие слов представьте и выставка незаметно, не режет слух. В основном подкорпусе Национального корпуса русского языка сочетание представить на выставке встречается более тысячи раз. 

Это не тавтология. Слово поздравляю в приведенном примере не является пожеланием здоровья, оно уже утратило это значение.

Инцидент приятным не бывает. А неприятный инцидент - плеоназм (лексически избыточное сочетание).