Find optimal figure size to fit two images on one page

The following example assumes that the images can be scaled to the half of the text height, then the example measures the height of the captions and calculates the available height for the images.

\documentclass{article}
\usepackage[pass,showframe]{geometry}

\newsavebox\CaptionBoxA
\newsavebox\CaptionBoxB
\newlength\ImgHeight   

\begin{document}

\begin{figure}
  \vbox to \textheight{%
    \centering
    \setbox\CaptionBoxA=\vbox{%
      \begingroup % color support
        \centering
        \caption{My first figure}%
        \label{fig:first}%
      \endgroup
    }
    \setbox\CaptionBoxB=\vbox{%
      \begingroup % color support
        \centering
        \caption{My second figure}%
        \label{fig:second}%
      \endgroup
    }
    \setlength{\ImgHeight}{%
      .5\dimexpr\textheight 
        -\ht\CaptionBoxA-\dp\CaptionBoxA
        -\ht\CaptionBoxB-\dp\CaptionBoxB
        -\floatsep
      \relax
    }

    \rule{10mm}{\ImgHeight}%
    % \includegraphics[height=\ImgHeight,width=\linewidth,keepaspectratio]{...}

    \unvbox\CaptionBoxA

    \vspace{\floatsep}
    \vspace{0pt minus .25\floatsep}% glue for safety
    \vspace{0pt plus 1fil}% glue for smaller images 
    \nointerlineskip % interline skip affects the calculation of \ImgHeight

    \rule{10mm}{\ImgHeight}
    % \includegraphics[height=\ImgHeight,width=\linewidth,keepaspectratio]{...}

    \unvbox\CaptionBoxB
    % \vspace{0pt plus 1fil}% glue for smaller images
}
\end{figure}

\end{document}

Result with paper size A5 and rules instead of images:

Remarks:

• The code would have to be put in a macro for practical usage.
• There is room for improvements. For example, the available space is equally distributed among the images. If one image cannot be scaled to the available space because of width limitations, then the other image could grow.
• There is room for extensions (three and more images, ...).

Edit: I think that @Heiko Oberdiek's answer is way more pro than mine. These are just a couple tricks. I'm not even sure why, but so far, these seem to work for me.

Maybe this answer is not even very TeX-like, but I'm a graphic designer with some experience, and just based on sheer amount of trial and error routines in the past, I am now accustomed to get two/three figures per page (or more) using a size of 45% the text height for two vertical images, or 45% the text width, for the horizontal ones. Use 30% for three images, etc. The trick is always leave around 10% of the \textwhatever free. It also helps a lot placing figures inside minipages, see this example (adapted to latex from other examples found in the LyX Wiki):

\documentclass[10pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4}
\usepackage{graphicx}

% Remember that line breaks matter. 
\begin{document}
% this some image i have, use your own...
\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}\hfill{}%
\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}\hfill{}%
\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}\\
[0.25cm]

\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}\\
[0.25cm]\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}\hfill{}%
\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

Several images in one page.%
\end{minipage}\hfill{}%
\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}\\
[0.25cm]\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}\\
[0.25cm]

\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}\hfill{}%
\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}\hfill{}%
\begin{minipage}[c][1\totalheight][t]{0.3\columnwidth}%
\centering

\includegraphics[width=1\textwidth]{img/_orig/c2/c2-img2}%
\end{minipage}
\end{document}