Table Formatting Suggestion

I'd recommend the usage of the booktabs package especially the use of its \cmidrule command with which you can easily overcome the drawback that you listed for your second table. I have also used the tabularx package that might come in handy, if the contents of your first column get longer than they currently are as the X type column allows for automated line breaks and ensures that the whole table is exactly as wide as the specified length (\linewidth in case of the following MWE):

\documentclass{article}

\usepackage{multirow}
\usepackage{pdflscape}
\usepackage{booktabs}
\usepackage{tabularx}

\begin{document}

\begin{landscape}

\section{Tables}


\begin{table}[ht]
    \begin{tabularx}{\linewidth}{Xccccccccc} \toprule
         & \multicolumn{3}{c}{No Clustering} & \multicolumn{3}{c}{$K$-means Clustering} & \multicolumn{3}{c}{Hierarchical Clustering} \\ 
         & \multicolumn{3}{c}{--} & \multicolumn{3}{c}{$K=2$} & \multicolumn{3}{c}{$K=5$} \\   
         \cmidrule(r){2-4} \cmidrule(lr){5-7} \cmidrule(l){8-10}
         & Lasso & Elastic Net & pcLasso & gLasso & sgLasso & pcLasso & gLasso & sgLasso & pcLasso \\ \midrule
        Tuning Parameters & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ \\ 
         & -- & $\alpha = 0.8$ & $\texttt{rat} = 0.95$ & -- & $\alpha = $ & $\texttt{rat} = 0.95$ & -- & $\alpha = $ & $\texttt{rat} = 0.95$ \\ \addlinespace
        Misclassifications & $5/36$ & $3/36$ & $3/36$ & $5/36$ & $/36$ & $2/36$ & $4/36$ & $/36$ & $2/36$ \\
        Non-zero Coefficients & $14$ & $28$ & $41$ & $7129$ &  & $62$ & $2714$ &  & $46$ \\
        Non-zero Groups & -- & -- & -- & $2$ &  &  & $2$ &  &  \\ \bottomrule
    \end{tabularx}
    \caption{The performance of various models on the leukemia data set.}
    \label{leuktable}
\end{table}
\end{landscape}

\end{document}

How about this layout? I've put the caption above the table, which is the typographic traditional position, for obvious reasons. The booktabs package defines horizontal rules with variable thickness and some vertical padding above and below. Furthermore, the \cmidrules can help visualise the groups of columns, using their optional trimming arguments l and r:

\documentclass{article}
\usepackage{multirow}
\usepackage{booktabs, caption}
\usepackage[usestackEOL]{stackengine}
\usepackage{pdflscape}

\begin{document}

\begin{landscape}

\section{Tables}

\begin{table}[ht]
    \centering
    \def\arraystretch{1.5}
\setlength{\cmidrulewidth}{\lightrulewidth}
\setlength{\tabcolsep}{4pt}
    \caption{The performance of various models on the leukemia data set.}
    \label{leuktable}
    \begin{tabular}{@{\,}lccc@{\qquad}ccc@{\qquad}ccc@{\,}}%
         & \multicolumn{3}{c}{\shortstack{No Clustering\\ --}\hspace*{2.5em}} & \multicolumn{3}{c}{\shortstack{$K$-means Clustering \\ $K = 2$}\hspace*{2.5em}} & \multicolumn{3}{c}{\shortstack{Hierarchical Clustering\\$K = 5$}\hspace*{0.5em}} \\
         \cmidrule(r{2.5em}){2-4} \cmidrule(r{2.5em}){5-7} \cmidrule(r{0.5em}){8-10}
         & Lasso & Elastic Net & pcLasso & gLasso & sgLasso & pcLasso & gLasso & sgLasso & pcLasso \\ \midrule
        \multirow{1.75}{*}{Tuning Parameters} & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ & $\lambda = $ \\[-1.5ex]
         & -- & $\alpha = 0.8$ & $\texttt{rat} = 0.95$ & -- & $\alpha = $ & $\texttt{rat} = 0.95$ & -- & $\alpha = $ & $\texttt{rat} = 0.95$ \\
\addlinespace[0.5ex]
        Misclassifications & $5/36$ & $3/36$ & $3/36$ & $5/36$ & $/36$ & $2/36$ & $4/36$ & $/36$ & $2/36$ \\
\addlinespace[0.5ex]
        Non-zero Coefficients & $14$ & $28$ & $41$ & $7129$ & & $62$ & $2714$ & & $46$ \\
\addlinespace[0.5ex]
        Non-zero Groups & -- & -- & -- & $2$ & & & $2$ & & \\ \bottomrule
    \end{tabular}

\end{table}

\end{landscape}

\end{document}