I am not sure whether or not attaching furigana changes the nuance of politeness. My question:
Is it rude to always attach furigana to every Kanji used in letters directed to superiors?
Note: the superiors are Japanese native speakers.
If I did so, yes, it would be very rude, because I am a native Japanese speaker who is supposed to be able to use fluent business Japanese. They might think I did so because I wanted to treat them as a small kid.
If you did so, and if the receiver knows you are not a native Japanese speaker, they probably wouldn't feel offended. But it would look very weird anyway. After all, no one has ever received such a letter.
A letter full of furigana is not just unnecessary; its complicated appearance can even prevent us from reading smoothly. If you know some of your kanji usages are very difficult, only use furigana for those words. If you feel some of your kanji usages may cause confusion and don't have time to ask here, just replace those words with hiragana. If you are worried about the fact that some words have two or more readings (eg 人気【にんき】 and 人気【ひとけ】), don't worry, Japanese native readers are good enough to handle such situations almost unconsciously.