Форма творительного падежа от названия города Балашова: Балашовом. В русском языке существует правило, согласно которому топонимы на -ов, -ев-, -ин, -ын, -ово, -ево, -ино, -ыно в творительном падеже имеют окончание -ом  — в отличие от имеющих те же финали фамилий славянского происхождения, которые в творительном падеже получают окончание -ым: под городом Балашовом — с Иваном Балашовым.  

Иноязычные названия, оканчивающиеся на -и, обычно не склоняются в русском языке.

Тире ставить не нужно. Между подлежащим библиотека и сказуемым ровесница находится обстоятельство фактически.

Вы включили в этот перечень совершенно разные с точки зрения грамматики названия. Осло, Торонто – иноязычные названия, они не склоняются. А вот Люблино, Бирюлёво, Орехово-Борисово – славянские топонимы, они всегда склонялись и продолжают склоняться. Подробнее о таких названиях см. здесь. 

В этом названии при отсутствии родового слова город должны склоняться обе части: Восточного Сараева, Восточному Сараеву, Восточным Сараевом, в Восточном Сараеве.

Вводные слова обособляются и в таких случаях.

На согласование по среднему роду влияет внешний облик этого слова (оно несклоняемое, оканчивается на гласный, ср.: «Динамо» забило, «Торпедо» вылетело). Да и с родовой принадлежностью названия города тоже не всё однозначно: словарь Е. А. Левашова «Географические названия» указывает, что название города Тосно может употребляться как существительное мужского и среднего рода, а «Грамматический словарь русского языка» А. А. Зализняка фиксирует Тосно как существительное только среднего рода.

Таким образом, можно говорить о допустимости согласования и по мужскому роду (влияние родовых слов город, футбольный клуб), и по среднему роду (влияние внешнего фонетического облика названия).

С большой буквы пишется только первое слово: Старый город. Это указано в орфографическом словаре РАН.

Оба варианта корректны.
 

Название города следует склонять. Подробнее см. в «Письмовнике».