El tema del relleno, lo arreglas cambiando el modelo de caja.
Y lo del select, siempre son especialitos. Lo más fácil es quitarle la apariencia.
Déjalo tal que así:
Código CSS:
Ver originalbox-sizing: border-box;
appearance: none;
Y luego quitar la altura (yo creo que es mejor usar rellenos y tamaño de la fuente) y ya solamente añadir un color de fondo.
Quedaría así:
https://jsfiddle.net/e9fgrrsd/1
Para recuperar la flecha del select puedes hacerlo con un pseudo elemento solo en el select.