Double-spaced paragraphs, single-spaced headers
You can use the etoolbox package to insert \singlespacing just before the sectional units, and then to append \doublespacing:
\documentclass{article}
\usepackage{setspace}
\usepackage{etoolbox}
\makeatletter
\pretocmd{\@sect}{\singlespacing}{}{}
\pretocmd{\@ssect}{\singlespacing}{}{}
\apptocmd{\@sect}{\doublespacing}{}{}
\apptocmd{\@ssect}{\doublespacing}{}{}
\makeatother
\doublespacing
\begin{document}
Nunc venenatis nulla eu arcu pellentesque eu molestie nunc condimentum.
Donec sodales lacinia dictum.
Sed aliquam turpis quis enim bibendum pharetra.
This is the last paragraph in section i.
\section{The Next Section Which Has a Fairly Long Name that Stretches Over Two Lines}
This is the first paragraph in section i+1.
Cras ut tortor vel dui ultricies dapibus vitae sit amet nisi.
Aliquam rhoncus leo id eros volutpat faucibus.
Integer lectus elit, varius et semper eget, tristique vel odio.
\end{document}
This will apply to \section, \subsection, \subsubsection.
Another option is to use the titlesec package:
\documentclass{article}
\usepackage{setspace}
\usepackage{titlesec}
\titleformat{\section}
{\singlespacing\normalfont\Large\bfseries}{\thesection}{1em}{}
\titleformat{\subsection}
{\singlespacing\normalfont\large\bfseries}{\thesubsection}{1em}{}
\titleformat{\subsubsection}
{\singlespacing\normalfont\normalsize\bfseries}{\thesubsubsection}{1em}{}
\doublespacing
\begin{document}
Nunc venenatis nulla eu arcu pellentesque eu molestie nunc condimentum.
Donec sodales lacinia dictum.
Sed aliquam turpis quis enim bibendum pharetra.
This is the last paragraph in section i.
\section{The Next Section Which Has a Fairly Long Name that Stretches Over Two Lines}
This is the first paragraph in section i+1.
Cras ut tortor vel dui ultricies dapibus vitae sit amet nisi.
Aliquam rhoncus leo id eros volutpat faucibus.
Integer lectus elit, varius et semper eget, tristique vel odio.
\end{document}
Or, using the reduced syntax:
\usepackage{titlesec}
\titleformat*{\section}{\normalfont\Large\bfseries\singlespacing}
\titleformat*{\subsection}{\normalfont\large\bfseries\singlespacing}
\titleformat*{\subsubsection}{\normalfont\normalsize\bfseries\singlespacing}
By the way, the setspace package provides several commands and environments; the commands (switches) end in "ing": \singlespacing, \onehalfspacing, \doublespacing, whereas the environments are singlespace, onehalfspace, doublespace.
Using \doublespace are you are doing (as a switch) is not entirely correct; the following simple document:
\documentclass{article}
\usepackage{setspace}
\doublespace
\begin{document}
test
\end{document}
when processed will show in the output console a message
(\end occurred inside a group at level 1)
### semi simple group (level 1) entered at line 4 (\begingroup)
which indicates that a group started but was never ended (in this case, the group created by the \doublespace command associated to the environment doublespace). The correct form of using the switch is
\documentclass{article}
\usepackage{setspace}
\doublespacing
\begin{document}
test
\end{document}
and, for the corresponding environment:
\documentclass{article}
\usepackage{setspace}
\begin{document}
\begin{doublespace}
test...
\end{doublespace}
\end{document}
If one of the "standard" document classes -- article, report, and book -- or a document class that's based on one of the standard classes is in use, a straightforward solution consists in loading the sectsty package and issuing the instruction \allsectionsfont{\singlespacing} in the preamble.
An MWE (minimum working example):
\documentclass{article}
\usepackage{setspace,lipsum}
\doublespacing
\usepackage{sectsty}
\allsectionsfont{\singlespacing}
\begin{document}
\lipsum[1] % filler text
\section{The Next Section Which Has a Fairly Long Name that Stretches Over Two Lines}
\lipsum[2] % more filler text
\end{document}