A lossy dielectric-lined (DL) waveguide is inherent with excellent mode-selective-propagation ability. A millimeter-wave gyrotron-traveling-wave (gyro-TWT) amplifier based on such kind of waveguide is characterized with high stability. In this paper, the analytical expressions of the field components of the operating modes in the DL waveguide are obtained from the eigenequation, and the linear theory of electron-cyclotron-maser (ECM) instability in the DL waveguide is developed by employing the full-wave-interaction method. This linear theory takes the waveguide structure and the characteristics of the lossy dielectric material into consideration. It is capable of accurately calculating the ECM instability between a cyclotron harmonic and a circular polarized mode, as well as effectively predicting the linear stability of the DL-waveguide-based interaction system. The validity of the linear theory is verified via comparing with results obtained using a coherently developed self-consistent nonlinear theory. Numerical calculation reveals a series of interesting results. This paper provides specific guidance for future designs of millimeter-wave lossy dielectric-loaded gyro-TWTs.