At the outset, it's important to remember that Doctor Who is not, in general, beholden to its own continuity. Any episode can, and frequently does, change virtually any statement made in a previous episode1. So take any notion of continuity you may have with a TARDIS-sized grain of salt.
Personally I advise watching in release order, because you'll experience the evolution of the show from "educational children's serial" to "cornerstone of British popular culture". That's what I did when I first got into Doctor Who, and I wouldn't have had it any other way.
It's also common to recommend watching the newer stuff before older stuff, whether older means pre-1966 or pre-1989 or something else entirely. There's generally logic to this, as the series has (as a general trend) gotten more reliably watchable2 as the years went on. And of course every fan has their personal favourite "hook" episodes - "Blink" and "City of Death" are some of the more common ones to hold this honour.
Ultimately, if you're going to watch the whole 800+ episode run either way, it doesn't really matter. Pick your favourite eras and start with those.
However, there are some things to keep in mind, which I'll try to go through in more-or-less decreasing order of importance.
Episodes vs. Stories
You have to remember that the classic Doctor Who was scripted, filmed, and broadcast in a serialized format, with weekly episodes that comprised parts of larger plots. For this reason, it's common to use the term "episode" to refer to a single airing of the show, and "story" to refer to the multi-week arcs.
The length of each story varied, although after the transition to colour in 1967 they were general consistent within a season3. Aside from one one-off (which was actually a prequel to a later story), they ranged from two episodes long up to a memorable twelve-part epic, with most at either three or four episodes.
Watch the episodes in any given story in broadcast order. That's how they were written, that's how the narrative unfolds, and that's how they should be consumed. There's a solid case to be made to watch each episode a week apart, since that's how the show was originally broadcast; while it would certainly improve the pacing of some of the weaker stories, that may take a prohibitively long time to do4.
Season-long arcs
In the new series, this sort of thing is represented by the "arc words" that typically characterize series3 - "Bad Wolf" in series 1, "Silence will fall" in series 5, etc. These aren't really arcs, but rather a loose grouping of episodes under a common theme. You can watch these in any order.
A similar thing occurs in season 8, where the character of The Master was introduced and appeared in every story of that season. In general the stories don't rely on each other, so you can also watch these in any order.
There are two other season-long arcs in Doctor Who: The Key to Time arc of season 16, and The Trial of a Time Lord arc of season 23. Each story in these arcs really do build to a larger point, so these stories should be watched in order.
Sort of tangentially related to this premise is season 12, the Fourth Doctor's first season. While not actually an "arc", per se, the episodes are pieces of the larger story of the Doctor and his companions trying to get back to Earth. It's not essential that you watch them in order, but it also doesn't hurt to.
Similarly, series 1 and 2 had a recurring subplot in the form of Rose Tyler's family back in England, a weird genre mashup between Doctor Who and British soaps that the TARDIS Eruditorium called EastPowellStreet. In typical soap opera style, the characters of EastPowellStreet (mainly Rose's parents Pete and Jackie, and her (ex-)boyfriend Mickey) have a kind of character arc that weaves through the Doctor Who story they get thrown into. Whether you want to watch this arc in order depends on how invested you are in the EastPowellStreet characters, really.
Another sort-of arc, in the new series this time, is the "The X of the Doctor" trilogy (quadrilogy, if you count the short "The Night of the Doctor"), "The Name of the Doctor", "The Day of the Doctor", and "The Time of the Doctor". This trilogy has a very definite character arc for the Eleventh Doctor, but plot-wise it's not essential that you watch in order.
Two- and three-parters
Distinct from the notion of stories are their last remnant in the revived series: the two-parter. Two-part episodes have been an occasional mainstay of the show since its revival in 2005, most often in series finales:
These should be watched in broadcast order.
There are also two three-part arcs in the revived series:
There are also two three-story arcs in the classic series:
- Season 18's E-Space trilogy ("Full Circle", "State of Decay", and "Warrior's Gate") form a narrative of the Doctor and Romana getting stuck in E-Space (negative spatial coordinates), and then trying to get back out. This trilogy also serves as the introduction of Adric as a companion, and Romana and K-9's departures
- Season 20's Black Guardian Trilogy. This trio of stories ("Mawdryn Undead", "Terminus", and "Enlightenment") are linked by newly-minted companion Turlough, who struggles with whether or not to betray the Doctor to advance his own interests.
Each of these arcs should be watched in broadcast order, because they form a single narrative.
The River Song Arc
River Song gets her own subheading, because she is a very odd case. Each of her occasional episodes is part of a larger romantic subplot between her and the Doctor, but the trick is that River is also a time traveller so the relationship is developed out-of-order. If you want to watch the development from the Doctor's point of view, then watch in broadcast order. If you want to watch it from River's point of view, the order is very different, and covered admirably by billpg's answer to another question.
Spoilers/Plot-relevant References
There are occasionally episodes that answer questions posted in previous episodes (or stories, as the case may be), or have otherwise-significant ties to previous episodes. It's generally pretty rare, especially in the classic series, but I'll try and keep a quasi-complete listing below:
Series 2 episode 3, "School Reunion", features the return of Sarah Jane Smith and K-9, companions last seen around season 15. Although you won't have trouble understanding the plot if you're not familiar with them, the emotional beats of the episode will fall flat.
Watch series 2 before series 3. A huge subplot of series 3 doesn't make any sense until you've seen "Doomsday", the series 2 finale.
Rose Tyler, companion for series 1 and 2, and a major love interest for the Doctor, gets trapped in a parallel universe.
"The Web of Fear" (fifth story of season 5), is a direct sequel to the earlier story "The Abominable Snowmen", the second story of season 2. They should be watched in that order.
Similarly, series 6 episode 12 "Closing Time" is a sequel to series 5 episode 11 "The Lodger". The fact that it's a sequel isn't terribly important to the plot, but the story does assume you're more-or-less familiar with the characters.
One more, series 1 episode 11 "Boom Town" is a sort-of sequel to the earlier two-parter "Aliens of London"/"World War 3". Again, the story assumes you're familiar with a character and the events of those episodes.
"The Angels Take Manhattan" and "The Snowmen", respectively the fifth episode of series 7 and the 2012 Christmas special. Those should absolutely be watched in that order, because, as above, the Doctor's motivations and behaviour change radically in "The Snowmen", for reasons that are part of the climax of "The Angels Take Manhattan".
The reason is that Amy and Rory, companions for the entire Matt Smith run up to that point, are traumatically lost to him
The tenth anniversary story "The Three Doctors" is a prequel to the first story of season 20 "Arc of Infinity". The later story continues the story of the main villain from "The Three Doctors", though I don't recall if they make any specific references.
The Black Guardian Trilogy (mentioned above) is a sequel to the earlier Key to Time arc (also mentioned above), and should be watched in that order. I don't recall if there are spoilers, but it gives the villain understandable motivations.
Watch "Earthshock" (story 6 of season 19) before "Time-Flight". The opening of the latter episode relies heavily on the ending of the former.
At the end of "Earthshock", companion Adric dies dramatically. The opening of "Time-Flight" has the remaining companions coming to terms with this.
In series 5 episode 12 "The Pandorica Opens", a major-ish plot point is the return of a character last seen in series 5 episode 9 "Cold Blood". The circumstances of the character's last appearance mean you should probably watch "Cold Blood" first.
The character is Rory Williams, who had been killed and then erased from time at the end of "Cold Blood." His appearance in "The Pandorica Opens" is a major clue about the situation facing the Doctor and Amy in that episode.
I advise against watching any episode featuring River Song that was broadcast after "A Good Man Goes to War" (series 6, episode 7) unless you've first seen that episode. It reveals a major secret about River's character that, while not essential to understanding her later appearances, is frequently referenced.
The secret is that River is Amy and Rory's adult daughter, and that she has a certain amount of Time Lord DNA that gives her the ability to regenerate and fly the TARDIS.
Don't watch the 2015 Christmas special ("Last Christmas") before you've seen the series 8 two-part finale "Dark Water"/"Death in Heaven". Occasionally referenced in "Last Christmas" is a major plot point of "Dark Water"/"Death in Heaven":
The death of Danny Pink, companion Clara Oswald's boyfriend/love interest
Season 20, episode 2 "Snakedance" (a Fifth Doctor story) is a direct sequel to the season 19 episode "Kinda" (pronounced kin-da, not kine-a). Aside from featuring the return of a monster (not unusual for Who), the plot of "Snakedance" follows directly from events in "Kinda". It could be confusing if you don't know what happened.
What happened in "Kinda" was that Tegan, the Doctor's companion, was possessed by a snake-demon called the Mara. While it ultimately gets banished, it returns in "Snakedance" and attempts to reassert itself in Tegan's mind.
Multi-Doctor Stories
Occasionally, typically for special occasions, the show airs an episode that features a previously-departed Doctor (and usually some companions from that era). You won't get as much out of these stories if you don't have a familiarity with all the guest stars.
- "The Three Doctors". Doctor Who's tenth anniversary special features the Second Doctor as a guest star, with a brief cameo by the First Doctor. The star of the show is, of course, the Third Doctor.
- "The Five Doctors". This was the show's twentieth anniversary, and featured a plethora of returning faces alongside the current Fifth Doctor and companions:
- The First Doctor (played by Richard Hurndall, as William Hartnell had died some years earlier) and Susan Foreman
- The Second Doctor, with cameos by Jamie McCrimmon and Zoe Heriot
- The Third Doctor, Brigadier Lethbridge-Stewart, Sarah Jane Smith, and cameos by K-9, Mike Yates, and Liz Shaw
- The Fourth Doctor and Romana have a cameo appearance through file footage (taken from an unaired episode), as Tom Baker declined the offer to return
- "The Two Doctors". Not an anniversary for once, this episode features the return of the Second Doctor and Jamie McCrimmon alongside the current stars, the Sixth Doctor and Peri Brown.
- "Dimensions in Time". A Children in Need charity special released for the show's 30th anniversary5, "Dimensions in Time" features the most returning stars of any Doctor Who television piece (I can't speak to the novels):
- The First and Second Doctors appear in still images. First Doctor companion Susan Foreman and Second Doctor companion Victoria Watterfield both appear
- The Third Doctor, Brigadier Lethbridge-Stewart, Mike Yates, Liz Shaw, and Sarah Jane Smith
- The Fourth Doctor, K-9, Leela, and Romana II (Lalla Ward)
- The Fifth Doctor and Nyssa
- The Sixth Doctor, Peri Brown, and Mel Bush
- The Seventh Doctor and Ace
"Dimensions in Time" was also a crossover with the British soap EastEnders. Characters from that show play important roles, but going over them is beyond the scope of this question.
Although not generally considered canon, I'm including it both for completeness and because it was the 30th anniversary special.
- "Time Crash" Another Children in Need charity special, released in 2007, "Time Crash" features the Fifth Doctor. The Tenth Doctor is the star of the show.
- "The Name of the Doctor". The series 7 finale and lead-in to the 50th anniversary special, this episode features all of the previous Doctors (along with the Eleventh Doctor) appearing in some form through judicious use of archive footage. Since they play no significant role in the story proper, it's less critical that you be familiar with them
- "The Day of the Doctor". The 50th anniversary special featured the Eleventh Doctor alongside the returning Tenth Doctor. The other Nine Doctors appear in cameos thanks to the magic of archive footage.
- "Deep Breath". The recently-departed Eleventh Doctor makes a brief cameo at the end of this episode.
The Brigadier
A special case to the above, Brigadier Sir Alistair Gordon Lethbridge-Stewart is the longest-running guest star on the show, appearing alongside every Doctor in the classic series at one point or another. Although less important in his earliest appearances, his status as a long-time acquaintance of the Doctor gets played up more and more as the series ages. The Brig's daughter, Kate Lethbridge-Stewart, has recently taken up the torch with her acquaintance with both the Eleventh and Twelfth Doctors.
Companions
Obviously the Doctor has had many travelling companions over the years, and they tend to come and go at irregular intervals. If you're watching the show out of order, it may be confusing for you to see companions pop in and out of existence like exotic particles. It's much less important than other things I've mentioned, but if you want to keep consistency with Companions you can find everything you need on Wikipedia.
On occasion, a companion will return after their formal departure. This never happened in the classic era to my recollection, but has happened a handful of times in the revived series (not counting cameos, of which there are several more in both eras):
- Rose Tyler returns in "Turn Left", "The Stolen Earth", and "Journey's End" after officially departing the show in "Doomsday"
- Jack Harkness returns in "Utopia", "The Sound of Drums", "Last of the Time Lords", "The Stolen Earth", and "Journey's End", after leaving the TARDIS in "The Parting of the Ways"
- Sarah Jane Smith and K-9, who last appeared as a companion back in (respectively) "The Hand of Fear" and "Warrior's Gate" but made a guest appearance in "School Reunion", returns for "The Stolen Earth", and "Journey's End"
- Martha Jones returns for "The Sontaran Stratagem", "The Poison Sky", "The Doctor's Daughter", "The Stolen Earth", and "Journey's End", after her last regular appearance in "Last of the Time Lords"
- Donna Noble initially appeared in "The Runaway Bride" as a one-off character, but returned as the regular Companion for series 4, beginning with "Partners in Crime"
- Rory Williams briefly left as a companion in "Cold Blood", but returned quickly in "The Pandorica Opens"
- Amy Pond, regular companion of the Eleventh Doctor from series five to the first have of series seven, made a cameo appearance in "The Time of the Doctor"
Although not strictly necessary, it's useful to be familiar with these companions before watching any guest appearances (or the reverse, in Donna's case).
Doctor departures
Similar to the above (although less critical in my opinion) is the fact that, obviously, the Doctor himself changes from time to time. Although this is largely not a problem if you're watching the show out of order, the personality switches can be a bit jarring if you're switching between dramatically different eras - you could go from Chris Eccleston being elated that "everybody lives" in "The Doctor Dances" to William Hartnell about to brain a caveman with a rock in "100,000 B.C." (part 2 of "An Unearthly Child"). If you want to maintain that sort of consistency, you may find it useful to bear in mind the span of episodes in which each Doctor appears. The Wikipedia article on Regeneration has a decent list of regeneration episodes, which should help inform your viewing.
In-jokes
This is the most common thing you miss by not watching in broadcast order.
One of the inevitabilities of being such a long-running, popular show is that eventually you'll be run by people who grew up as fans of the show. The early seasons of John Nathan-Turner's run as lead producer (seasons 19-22)6 is one such time, but it's become most noticeable in the revived series7. Writers in these eras in particular are fond of including sly, blink-and-you-miss it references to past episodes. These references are generally not required to understand the episode you're watching.
A perfect example occurs in series 5, episode 6 "The Vampires of Venice", an Eleventh Doctor story. At one point in the episode, the Doctor mistakenly pulls out an old library card featuring the First Doctor's face:
These jokes are meant to reward long-time viewers of the series, so it's not critical that you understand the reference.
I have no doubt that this is far from an exhaustive list (and I'm sure the commenters will converge soon pointing out various omissions), but as a general note I want to point out that Wikipedia has a remarkably detailed entry for every episode (or story) of Doctor Who, ~99% of which include a "Continuity" section. This section details most (though not necessarily all) of the back-references in the given episode/story, from the trivial name-dropping to more significant plot points. This is a very good resource for doing research on an episode-by-episode basis.
1 To the point where the show has provided two incompatible alien origins for the Loch Ness Monster, three different accounts of the sinking of Atlantis, hilariously convoluted histories for both the Daleks and Cybermen, and several truly cosmic retcons for the Doctor himself.
2 With a generally-agree-upon rough patch around series 20-24
3 I'll be using "series" to refer to post-2005 seasons, and "season" to refer to 1963-1989 seasons.
4 Classic-series episodes were typically 25 minutes each, although in season 22 they were upped to 45 minutes (though fewer were commissioned - it was a rough time for the show), and the classic series had 696 of them. That's a lot of weeks.
5 The special was released in 1993, four years after Doctor Who was officially cancelled. This makes it the first live-action Doctor Who of the Wilderness Years
6 This era is notable because Nathan-Turner retained the services of Ian Levine as a sort of unofficial "continuity advisor" for the show. A vocal superfan, Levine was one of the loudest voices for an increased engagement with the show's past. Whether or not this was ultimately a good thing is a matter of some debate
7 Many writers of post-2005 episodes, notably Mark Gatiss, Paul Cornell, and Russell T. Davies himself, all contributed to the line of Doctor Who novels published by Target Books between 1986 and 1997. Steven Moffat was also fairly well-known on Doctor Who newsgroups (Wikipedia link for younger readers who never heard of them), where (among other things) he initially put forth the theory that the Doctor inspires people to add the word "doctor" to their languages.
