En lo que respecta a Coliseo, la mayúscula resulta adecuada, pero para el gentilicio (romano) lo apropiado es la minúscula, pues no forma parte de su denominación. Es decir, se escribiría el Coliseo romano (con el artículo siempre en minúscula).

En otras denominaciones de edificios singulares o construcciones monumentales en las que al sustantivo coliseo le acompaña un término específico, podría utilizarse mayúscula o minúscula inicial, como señala la Ortografía de la lengua española: Coliseo/coliseo León XIII.

En plural no se alude a ningún edificio o conjunto monumental en concreto, por lo que en ese caso sería recomendable la minúscula: los coliseos.