Aside тоже должен уменьшаться?
Просто обычно колонки с меню выдерживаются в одной ширине. А на малых экранах либо пропадают, либо скрываются под кнопку, либо перемещаются под контент.
Я бы сделал aside постоянным, а внутри контентной области .col-md-4 для каждого блока.
Тут у вас используется display: inline-block; соответственно работает все как встроенный элемент.
Пространство возникает так как между встроенными элементами по умолчанию включаются пробелы, надо у nav сделать font-size: 0; а у блоков .logo и .search установить необходимые значения шрифта
Встроенные элементы по умолчанию выравниваются по вертикали: по базовой линии. Надо для .search и .logo поставить vertical-align: top;