An odd case where an attempted lack of fanservice just made the show even more enticing, as Barbara Eden's genie costume was famously risque, yet the NBC censors refused to let her navel be visible despite other shows of the era (most notably Gilligan's Island) being able to get away with occasional "flashes." This resulted in many a viewer closely watching each episode for the rare times that a navel slip made it in.
In general, whenever the show's infamous rivalry with Bewitched is discussed, one way of distinguish them apart is to mention something along the lines that I Dream of Jeannie was the one who had heaps of Fanservice. Even Supernatural had Dean's mind wandering in one episode where his brother Sam was discussing djinn with him, and Sam tells him that djinn are not "like Barbara Eden in harem pants."
Dean: My God. Barbara Eden was hot, wasn't she? Way hotter than that Bewitched chick.
Sam: Are you even listening to me?
Dueling Works: With Bewitched. 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.
Hilarious in Hindsight: In "Blackmail Order Bride", the woman who pretends to be Tony's wife is named Sue Ellen.
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.
They Copied It, So It Sucks!: The show's infamous rivalry with Bewitched stemmed in part from this. While many episodes share the basic plot of earlier Bewitched episodes, the two most infamous examples were giving the heroine an evil dark-haired twin relative (Cousin Serena/Jeannie's sister) and retconning Jeannie's backstory from being a former human into her coming from a family of genies, much like the situation on Bewitched. 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.
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.
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!