Tú mismo estás haciendo que esto ocurra así al declarar la propiedad display:block.
Eso hace que los enlaces <a> ocupen la totalidad del ancho disponible y fuerzan el salto de línea antes de mostrar el siguiente elemento.
Como tú has apuntado una solución sería hacer flotar los elementos.
Otra sería declararlos como display: inline-block. Esto haría que se mostrasen uno a continuación del otro aunque con el tamaño que tu les has dado.
Asegúrate de que la suma del tamaño de los elementos mas bordes, padding y margin quepan en el ancho de la página.
Perdón por ser tan lento. Ya habían contestado cuando he enviado la respuesta.