And why do we say "putting your best foot forward"? Unless you have 3 or more legs surely the expression should be "putting your better foot forward"...
Analogy... the word picture attempted by the phrase "head over heels" is someone tumbling out of control and head is following heels in the production... Here in the western U.S. our neighbor Nels says "ass over appetite"... same word picture though...
The original - created by James Joyce in his novel, Ulysses - was "arse over tiP", which makes more sense. The tiT variant did not appear until half a century later.
I think I know what's happened here. According to factor30's link, the original version was indeed 'heels over head', but with the cunning use of irony, people have actually turned the phrase itself 'heels over head' until it became 'head over heels'.