サンプル

基本のHTML

<div id="Nav">
 <ul class="clearfix">
  <li><a href="#">HOME</a></li>
  <li><a href="#">HTML&amp;CSS</a></li>
  <li><a href="#">Javascript&Ajax</a></li>
  <li><a href="#">PHP</a></li>
 </ul>
</div>

基本のCSS

#Nav { font-size: 1em; }
#Nav ul {
  margin: 0px;
  padding: 0px;
}
#Nav li {
  list-style: none;
  float: left;
}
#Nav a {
  display: block;
  margin: 0px 1px 0px 0px;
  padding: 0px 10px;
  border: 1px solid #0099FF;
  color: #0099FF;
  text-decoration: none;
  text-align: center;
}
#Nav a:hover {
  background: #FFACAC;
  color: #990000;
}

シンプルメニュー（上のコードをそのまま表示）

#Nav aにheight:30px;を追加

#Nav aにline-height:30px;を追加

#Nav aにfloat:leftを追加

#Nav aにfloat:leftとline-height:30px;を追加

結局、floatとline-heightを同時に指定するのが1番希望通りの動作になりました。