The vertical skip from baseline to baseline within regular text is given by \baselineskip. Within tabular, this is 0pt but it is still accessible as \normalbaselineskip. Using your example as reference, it is clear to see that the vertical baseline skip still holds when drawing a vertical 1pt rule of height \normalbaselineskip:
\documentclass{article}
\begin{document}
\begin{tabular}{*{5}{|c}|}
\hline
$p$ & $q$ & $p \land q$ & $p \lor q$ & $p \to q$\\
\hline
T & T & T\smash{\rule{1pt}{\normalbaselineskip}} & T & T\\
\hline
T & F & F & T & F\\
\hline
F & T & $f$ & T & T\\
\hline
F & F & F & F & T\\
\hline
\end{tabular}
\end{document}
If you have a very particular table, like the one in your example, where baseline alignment may seem to be inadequate, you could play around with the addition of a vertical "strut" like in the following example:
\documentclass{article}
\usepackage{array}% http://ctan.org/pkg/array
\begin{document}
\newlength{\mylen}\settowidth{\mylen}{$p \to q$}% Widest element
\begin{tabular}{*{5}{|>{\centering\arraybackslash\rule{0pt}{1.05em}}m{\mylen}}|}
\hline
$p$ & $q$ & $p \land q$ & $p \lor q$ & $p \to q$\\
\hline
T & T & T & T & T\\
\hline
T & F & F & T & F\\
\hline
F & T & F & T & T\\
\hline
F & F & F & F & T\\
\hline
\end{tabular}
\end{document}
Using the array package, it allows you to insert <stuff> before every table column entry using >{<stuff>}. Using the m{<width>} column specification, I've fixed the column widths (I think it looks cleaner that way) and reverted back to the centering supplied by c-columns.
Although this may be a moot point based on personal preference, consider using the booktabs package to typeset tables:
\documentclass{article}
\usepackage{array}% http://ctan.org/pkg/array
\usepackage{booktabs}% http://ctan.org/pkg/booktabs
\begin{document}
\newlength{\mylen}\settowidth{\mylen}{$p \to q$}% Widest element
\begin{tabular}{*{5}{>{\centering\arraybackslash}m{\mylen}}}
\toprule
$p$ & $q$ & $p \land q$ & $p \lor q$ & $p \to q$ \\
\midrule
T & T & T & T & T \\
T & F & F & T & F \\
F & T & F & T & T \\
F & F & F & F & T \\
\bottomrule
\end{tabular}
\end{document}
It's not clear that there is really an issue to be solved, it is only an issue for tables if you think there is an issue about tables. Most of the points that you raise could also be made about "paragraphs" or "lists", at some point you have to have some structural information as well as words.
It is easy to have an environment that defaults the column spec, consider for example the amsmath matrix which is more or less just array with a default supplied preamble of *{20}{c} so you could define
\newenvironment{mytab}[1][*{50}{c}]{%
\begin{tabular}{#1}}{%
\end{tabular}}
which makes the column specifications optional, defaulting to all centred. Unlike matrices though where a global default is commonly useful, in my experience a global table default is almost never useful, tables usually have varied column types, some textual, some numeric to be aligned on decimal points, etc. However if in a particular document you have a lot of tables all taking the same form you could use a definition as above, replacing *{50}{c} by say >{\bfseries}l *{2}{D..{3.2}} p{3cm} if all your tables have a bold left aligned column, two numeric columns and a final column of note paragraphs.
It's hard to guess how you could automate rules in general, If you always want a top and bottom rule you could change your definition to
\newenvironment{mytab}[1][*{50}{c}]{%
\begin{tabular}{#1}\toprule}{%
\\\bottomrule\end{tabular}}
But the position of \midrule is rather like the position of words and numbers in the table, effectively it's data that must be entered in each case. Perhaps you only want \midrule after the heading in which case you could use
\newcommand\endhead{\\\midrule}
so your tables would then look like
\begin{mytab}
\hd{type}&\hd{A}&\hd{B}&\hd{Notes}\endhead
zzz&1.2&3.4& zz zz zzzzz\\
zzz&1.2&3.4& zz zz zzzzz\\
\end{tab}
Using a heading command \hd that could be defined as
\newcommand\hd[1]{%
\multicolumn{1}{c}{\bfseries\begin{tabular}{@{}c@{}}#1\end{tabular}}
To give bold, centred, potentially multi-line table headings. Color could be added to this command as well if you want coloured tables, there is no need for explicit colours in the table.
Best Answer
Vertical centring of headings is most easily done with
tabularand I removedcenteras it doesn't centre longtables. I reduced the inter column spacing by a bit as your table was slightly too wide for the page.