You can resize it using \resizebox{<width>}{<height>} from the graphics package. The column width is \columnwidth and you can select ! for the height to make it scale along with the width.
\usepackage{graphics}
% ...
\begin{table}
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{r|lll}
\multicolumn{1}{r}{}
& \multicolumn{1}{l}{Heading 1}
& \multicolumn{1}{l}{Heading 2}
& \multicolumn{1}{l}{Heading 3} \\ \cline{2-4}
Row 1 & Cell 1,1 & Cell 1,2 & Cell 1,3 \\
Row 2 & Cell 2,1 & Cell 2,2 & Cell 2,3
\end{tabular}%
}
\end{table}
Should the table include verbatim or similar material than \resizebox isn't good enough. You can use the {adjustbox}{width=\columnwidth} environment from the adjustbox package instead. It is based on the same graphicx code as \resizebox but allows for any content.
Please do not use the center environment in floats (figure, table), it generates an extra margin and doesn't always work. Use the \centering macro instead.
Solution with adjustbox:
\usepackage{adjustbox}
% ...
\begin{table}
\begin{adjustbox}{width=\columnwidth,center}
\begin{tabular}{r|lll}
\multicolumn{1}{r}{}
& \multicolumn{1}{l}{Heading 1}
& \multicolumn{1}{l}{Heading 2}
& \multicolumn{1}{l}{Heading 3} \\ \cline{2-4}
Row 1 & Cell 1,1 & Cell 1,2 & Cell 1,3 \\
Row 2 & Cell 2,1 & Cell 2,2 & Cell 2,3
\end{tabular}
\end{adjustbox}
\end{table}
There's no \medium font size between \small and \large; you have \normalsize (which is the default font size). The standard font size switches are: \tiny, \scriptsize, \footnotesize, \small, \normalsize, \large, \Large, \LARGE, \huge, and \Huge.
By the way, you only need one font switch command inside the table and braces are not required since table forms a group, so you can simply say something like this:
\begin{table}
\small
\begin{tabular}{p{3.5cm}p{8cm}p{5cm}}
text & text & text
\end{tabular}
\end{table}
Best Answer
If you really want to make sure your table becomes unreadable, you can use the
\fontsizecommand to set the font size to whatever you like: