The main reason I see to use minipage over \parbox is to allow verbatim (\verb, verbatim, etc.) text inside the box (unless, of course, you also put the minipage inside a macro argument).
EDIT Here are other differences between minipage and \parbox (from the comments to Yiannis' answer and from looking at the source code of both these macros in source2e).
A first difference, as already mentioned by lockstep in his question, is in the footnote treatment: minipage handles them by putting them at the bottom of the box while footnotes are lost in a \parbox (to avoid this, you must resort to the \footnotemark/footnotetext trick):
\documentclass{article}
\begin{document}
\parbox[t]{3cm}{text\footnote{parbox footnote}}
\begin{minipage}[t]{3cm}text\footnote{minipage footnote}\end{minipage}
\end{document}
A second difference is in that minipage resets the \@listdepth counter, meaning that, inside a minipage, you don't have to worry about the list nesting level when using them. Here's an example which illustrates the point:
\documentclass{article}
\begin{document}
\begin{list}{}{}\item\begin{list}{}{}\item\begin{list}{}{}\item\begin{list}{}{}\item
\begin{list}{}{}\item\begin{list}{}{}
\item %\parbox{5cm}{\begin{list}{}{}\item \end{list}}% error
\item %\begin{minipage}{5cm}\begin{list}{}{}\item \end{list}\end{minipage}% no error
\end{list}\end{list}\end{list}\end{list}\end{list}\end{list}
\end{document}
A third difference is that minipage sets the boolean \@minipagefalse which in turn deactivates \addvspace if it's the first thing to occur inside a minipage. This means that minipage will have better spacing and allow better alignment compared to \parbox in some cases like the following (left is minipage, right is \parbox):
\documentclass{article}
\begin{document}
Pros: \begin{minipage}[t]{3cm}\begin{itemize}\item first \item second%
\end{itemize}\end{minipage}
Cons: \parbox[t]{3cm}{\begin{itemize}\item first \item second\end{itemize}}
\end{document}
This is more of an extended comment.
Alignment with minipage
You can use the adjustbox package to control vertical alignment of the image (load it before you load pstricks though).
Code
% compile with latex + dvipdfmx
\documentclass[]{beamer}
\mode<presentation>
\usepackage{mwe} % provides image in this example
\usepackage{adjustbox}
\usepackage{beamerthemesplit,mathtools,pgf,pstricks}
\setbeamertemplate{footline}[page number]
\begin{document}
\begin{frame}{with \texttt{minipage}}
\noindent
\begin{minipage}[t]{0.48\linewidth}
\adjustbox{valign=T}{\includegraphics[scale=0.4]{image.eps}}
\end{minipage}
\hfill%
\begin{minipage}[t]{0.48\linewidth}
\begin{itemize}
\item right part
\item test2
\item test3
\end{itemize}
\end{minipage}
\end{frame}
\end{document}
Output (despite a lot warnings during dvipdfmx)
Including a .eps image in columns
It is by chance that I come to discover that the contents in the frame with columns got "pushed" down and to the left for some reason during the latex+dvipdfmx compilation. This is illustrated by issuing \vspace{-7cm} in the following:
\documentclass[]{beamer}
\mode<presentation>
\usepackage{mwe} % provides image in this example
\usepackage{beamerthemesplit,mathtools,pgf,pstricks}
\setbeamertemplate{footline}[page number]
\begin{document}
\begin{frame}{with \texttt{columns}}
\vspace{-7cm}
\begin{columns}[T]
\column{.48\textwidth}
\includegraphics[scale=0.4]{image.eps}
\column{.48\textwidth}
\begin{itemize}
\item right part
\item test2
\item test3
\end{itemize}
\end{columns}
\end{frame}
\end{document}
I don't know why this is the case. It probably has to do with all the warnings one gets during the dvipdfmx run. Hopefully someone can answer this part of the question.
Best Answer
In short: this three environments are in the general case completely different.
minipagecreates a mini-page, i.e. you can place several paragraphs in a box and even have footnotes in it which are shown at the bottom. It is very often used to change the text width for some material and to avoid that it is broken over a page. It is also the way to draw a frame around paragraphs etc. It can be used to place two paragraphs or other things like images and tables side by side, but this is just one of its applications.columnsis abeamerenvironment and good for creating, aeh, columns! Like having bullet points on the left and a graphic on the right. For normal documents use themulticolsenvironment from themulticolpackage instead.tabularis an environment to create tables, usually with multiple columns and rows. It can also be used to place other material like images or other whole tables in an tabular form. You can put vertical lines in it, but this is actually not recommend because it is considered bad style (see the manual of the recommendedbooktabspackage).I can see one common application, which is to place things side by side. In this case you could use all three (only in beamer), but normally
minipageis used when you need vertical mode to add a caption (example) ortabularif you need are more complex design but don't need vertical mode (example). Anyway, in theory almost any combination of them is possible.