I'll probably get ripped into for this, but I'd listened to alot of old stuff from the 80's lately, and one of the better unknown solos was from Whitesnake's "Wings of the Storm." Starts out with this cool ambient sound effect-y arabic scale part, then goes into this dual trading guitar lick part and then ends with this nutso tapping run. I like it best because, unlike alot 80's solos, there's actually some pretty good phrasing involved, and it's not constant shred.
Also, George Lynch had some pretty sweet 80's solos, too. Great "80's" tone and phrasing.
Seconded on whoever said Jason Becker. "Altitudes" is amazing.
I've also always liked Andy Timmon's more "soulful" stuff. ("Gone", "Resolution") And since their instrumentals, they might as well be solos.
Got another Buckethead one too. "Humans Vanish" very "Maggot Brain"-ish, which should also be on this list.
I suppose another thing I always look for in a good solo/guitarist, is if you can tell without knowing the song, who's playing it.