Structured eigenvalue problems feature a prominent role in many algorithms for the computation of robust measures for the stability or controllability of a linear control system. Structures that typically arise are Hamiltonian, skew-Hamiltonian, and symplectic. The use of eigenvalue solvers that preserve such structures can enhance the reliability and efficiency of algorithms for robust stability and controllability measures. This aspect is the focus of the present work, which summarizes and extends existing structure-preserving eigenvalue solvers. Also, a new method for estimating the distance to uncontrollability in a cheap manner is presented. The structured eigenvalue algorithms described in this paper are intented to become part of HAPACK, a software package for solving structured eigenvalue problems and applications.