Корректно: А потом, не сговариваясь, оба поехали поступать в медицинский институт в Нижний Новгород.

В «Справочнике издателя и автора» А. Э. Мильчина, Л, К. Чельцовой дана такая рекомендация: названия участков течения рек и плесов пишутся со строчной, если они не входят в состав сложных собственных названий. Например: верхняя Припять, нижняя Березина, средний плес Волги. Но: Верхняя Тура (название города), Нижняя Тунгуска (название реки). Поэтому правильно: верхний Амур, средний Амур, нижний Амур.

Рекомендуем писать эти сочетания как описательные обороты со строчной буквы.

Требуется тире: По сообщениям, над районным центром — городом Нижний Ломов и прилегающей к нему сельской местностью ожидается гроза.

Что касается склонения названия, то справочники дают разные рекомендации. На практики названия из двух слов при употреблении с родовым словом город чаще не склоняются.