Да оба слова пишутся с большой буквы: Лосиный Остров.
Топонимы с родовым словом остров обычно не склоняются: на острове Кипр.
Географические названия: остров Путятина, остров Аскольд.
Топонимы в сочетании со словом остров обычно не склоняются. Поэтому верно: на острове Коневец. Подробнее см. в "Письмовнике".
Нужно склонять: тетрадь Деды Елены.
Правильно: остров Татышев.
Правильно: Остров свободы.
Об одном острове корректно: остров Курильской гряды.
Оба варианта окончаний корректны и используются. Более распространенным является вариант с окончанием -ой.
Правильно: остров Татышев (от имени Татыш).