The solution of the Conic Quadratic Eigenvalue Complementarity Problem (CQEiCP) is firstly investigated without assuming symmetry on the matrices defining the problem. A new sufficient condition for existence of solutions of CQEiCP is presented, extending to arbitrary pointed, closed and convex cones a condition known to hold when the cone is the nonnegative orthant. We also address the symmetric CQEiCP where all its defining matrices are symmetric. We show that, assuming that two of its defining matrices are positive definite, this symmetric CQEiCP reduces to the computation of a stationary point of an appropriate merit function on a convex set. Furthermore, we discuss the use of the so called Spectral Projected Gradient (SPG) algorithm for solving CQEiCP when the cone of interest is the second-order Cone (SOCQEiCP). A new algorithm is designed for the computation of the projections required by the SPG method to deal with SOCQEiCP. Numerical results are included to illustrate the efficiency of the SPG method and the new projection technique in practice.