Kidushin 31a brings the story of Dama ben Nesina and his amazing Kibud Av V'Aim which cost him a huge fortune. He was rewarded for his amazing Kibud Av V'Aim by one of his cows giving birth to a red heifer (Para Aduma) which was then sold for the same amount he previously lost by doing Kibud Av V'Aim. Why was there a need specifically for him to be rewarded in such a manner? Why could he not find a diamond that had such a value? Why reward him with a Para Aduma?
Ma'ayaneh Shel Torah quotes the The Chiddushei HaRIM that when Dama ben Nesina lost a huge sum of money because he was honoring his father, it created a Heavenly Accusation against the Jewish people.
By giving him a red heifer, G-d showed that while a non-Jew was willing to lose a large amount of money for a Mitzvah that makes sense, the Jews were willing to spend the same amount of money for a Mitzvah that is a Divine Decree and is completely irrational.
According to rashi in Bamidbar 19:22, in his second explanation of para aduma from rabi Moshe hadarshan, the para aduma comes to fix the mess from the eigel, just like the maidservant who cleans the mess in the palace that her child made.
Accordingly, the para aduma is representative of a good relationship between parent and child. Mr. Nesina was treated favorably by his son and the reward to the son was sign that his father was actually deserving of such behavior. As opposed to lets say his mother from story later in the gemara.
To demonstrate that although we see good rational reasons for kibbud av, we still must treat it as a chok and show unconditional observance even when it may not seem logical. This may be why it is listed in 10 commandments with the mitzvos between man and hashem and not with mitzvos between mam and man.
Similar to the last answer but a little more. The parah adumah is called "Zos Chukas Hatorah" not "Chukas Haparah" to show that like all Mitzvohs in the Torah - they are not done out of rational sense but because Hashem commanded it. The story of Dama illustrates this. He kept the most sensible and rational Mitzvah of Kibud Av and was rewarded by the totally irrational and supernatural Mitzvah of Parah. To show, we don't understand anything at all with our puny abilities and it's all the same Torah commandment to follow. I had heard he kept the Mitzvah of Kibud Av because it was commanded and not out of rational sense. If the latter, he would have found a reason to wake his father for the loss of money.
BTW- I had also heard that the reason it is listed on the right side of the Luchos as noted above is because acknowledging that one came from somewhere, i.e. parents , is an acknowledgement of Hashem's creation of the Universe and that's why its listed on the group of Commandments between Man and Hashem. (Also because Hashem in the third partner in creation of every Man in addition to the two parents). Likewise, Shabbos is on the right side of the Two Luchos , (actually there were two separate Luchos -not like the depiction of one Tablet with a right side and a left side), to acknowledge that Hashem created the World and , therefore, ceased Creation on Shabbos.