Ironically, many foreign dubs (the Italian, the Japanese, and the German dubs) changed Jeannie to be a witch. It is rumored that the dubbers mistook the show for a spin-off (or tried to retcon it into being one).
Ear Worm: The upbeat theme tune that was used from Season 2 on.
Evil Is Sexy: Wicked Jeannie, not that the Good Jeannie is any less...
Fair for Its Day: Tony explicitly freed Jeannie in the first episode, never took advantage of her Happiness in Slavery and consistently refused to exploit her powers for his own advancement — all fairly enlightened for a man of his era. So was his alleged desire for mundane conformity actually a sign of integrity? One could easily see how a man with enough drive to become an astronaut would not want a walking Deus ex Machina to just hand him the things he was intent on achieving on his own merits. Furthermore in a sense, though Jeannie thinks she's Tony's slave, she's disobedient to his orders, even when they're in her best interests.
"Funny Aneurysm" Moment: In "Mrs. Djinn-Djinn", a woman asks Jeannie whether she is pregnant. At the time, Barbara Eden was pregnant with her second child, but complications with it caused it, in short, to end in a miscarriage.
Ho Yay: Tony generally seems more interested in hanging out with his astronaut buddies than giving Jeannie, a pretty blonde in a harem girl costume who is willing to be his literal slave and bride, the time of day. The fact that he has no problem whatsoever with his fiancee, Melissa, leaving him also has shades of this.
The Man Show had a sketch that uses this trope to explain why Tony wouldn't be interested in a smoking hot genie.
Apparently, this was because the writer who developed Serena went to work for I Dream of Jeannie.
Values Dissonance: There was considerable controversy during the episodes where Jeannie's costume showed off her belly button. Modern viewers who hear about the bellybutton issue wonder why, since the rest of her costume consists of see-through harem pants and a top she spills out of, both of which would seem like a much more hot-button issue.
Vindicated by Cable: While the show was by no means a flop, and its cancellation was due more to it being the network's plaything than anything, the show did tremendously well in syndication.
The Woobie: Jeannie. Her tragic backstory consisted of being stripped of her humanity and being trapped in a bottle by a wicked djinn (though she was later retconned to have been born a genie), her mother and sister are outright evil, and Tony could be cruel to her.
Tony's treatment of Jeannie gets lampshaded in "Divorce, Jeannie Style", in which the Bellows meet Jeannie and mistake her for Tony's wife, and nearly bring Tony to the authorities over Domestic Abuse.
Her actress, Barbara Eden, counts as a woobie, too.
Dr. Bellows. How can you not feel sorry for him every now and then? Especially since he and Amanda are very friendly to Jeannie when they finally meet her!