Everyone's first starting point when dealing with the polynomial rootfinding problem should be a peer at J.M. McNamee's excellent bibliography and book.
Now, it is a fact that polynomials of very high degree tend to make most polynomial rootfinders choke. Even the standard blackbox, the Jenkins-Traub algorithm, can choke if not properly safeguarded. Eigenmethods, while they can have nice accuracy, can be very demanding of space and time (O(n²) space and O(n³) operations for a problem with only O(n) inputs!)
My point is that unless you are prepared to devote some time and extra precision, this is an insoluble problem.
Having been pessimistic in those last few sentences, one family of methods you might wish to peer at (and I have had personal success with) are the so-called "simultaneous iteration" methods. The simplest of them, (Weierstrass-)Durand-Kerner, is essentially an application of Newton's method to the Vieta formulae, treated as n equations in n unknowns (the assumption taken by (W)DK is that your polynomial is monic, but that is easily arranged).
If you wish for more details and references, the book by McNamee I mentioned earlier is a good start.