В названиях музеев с большой буквы пишется первое слово и входящие в состав названия имена собственные: Музей кукол, Государственный Русский музей, Государственный музей изобразительных искусств им. А. С. Пушкина.

Да, оба эти слова пишутся с прописной (большой) буквы при таком употреблении.

Сочетание Всероссийская олимпиада пишется с прописной буквы, только если словом Всероссийская начинается официальное полное название конкретной олимпиады. 

Оба варианта возможны. Сочетание в этой связи просторечным не является (см. его фиксацию в словарях: Правильность русской речи / Под ред. С. И. Ожегова. М., 1965, с. 184; Трудности словоупотребления и варианты норм русского литературного языка / Под ред. К. С. Горбачевича. Л., 1974, с. 401; Большой толковый словарь / Под ред. С. А. Кузнецова. СПб., 1999, с. 1164). Соответствуя норме современного русского литературного языка, это устойчивое cочетание употребляется как наречие со значением 'связывая со сказанным выше' и служит своеобразной формулой перехода от одной мысли к другой.

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

Вы написали правильно.

Правила таковы: имена прилагательные, обозначающие индивидуальную принадлежность, пишутся с прописной буквы, если они образованы от собственных имён при помощи суффикса -ов (-ев) или -ин: Юлина юбка, Машины пирожки (в составе фразеологических оборотов такие прилагательные пишутся со строчной буквы: ахиллесова пята, сидорова коза). Если же соответствующие прилагательные имеют в своём составе суффикс -ск-, они пишутся со строчной буквы: пушкинские стихи, петровские преобразования, булгаковский стиль.

Правильно: страны «Большой восьмерки».

Правильно: Римская империя.

Правильно: в лице президента – председателя правления. С большой буквы пишутся только названия высших государственных должностей.

Правильно: День российской науки.

Такая рекомендация не вполне справедлива.