My first song was Enter Sandman from Metallica. Because I was so into Killswitch engage, I tried My curse, but failed miserably after hours of trying. Rage against the Machine has some nice Songs; Freedom, Killing in the name... Mudvayne, Trivium, Parkway Drive,... Good luck with those ^^ and have fun practicing
Am I Evil by Diamond Head was one of the first metal songs I ever learned. It's a goody.
Manic Depression by Hendrix is a fun one too.
Breaking the Law by Judas Priest is cool.
Man, this has turned into a stroll down memory lane!
Also, don't sweat soloing too much- it'll come. When I started out, I couldn't play AC/DC solos, and now, I still can't play AC/DC solos.
Seriously, half the time I sound like a third grader and the other times I sound like a broken super-computer that has been programmed by the third grader.
If you want to learn some easy solos, I strongly suggest solos from Aerosmith, Guns n' roses and Metallica's stuff from "... In justice for all" and from the "Black album". Reason being is that their solos have strong melody in them and strong melody will help you hear where you are at in the solo.
Since you say you are pretty comfortable with the rhythm stuff of the songs you like, but need help with your leads, I would suggest learning some scales and then practicing the hell out of them. Just keep practicing your scales and you will see an improvement in your lead playing. Don't worry about speed, just be as precise as you can be.
Learn your scale modes (Phyrgian, Ionian, Locrian, Dorian, Lydian, Mixolydian, Aeolian etc) and mess around with the notes to create your own little lead runs. You can purchase the "Scale Wizard" app on the App Store for 0.99c and it's got all your scales across each position, as well as some more advanced scales and arpeggios.
Waters' advice in this video @ 3:00 - learn/practice Chemical Warfare (or anything off Show No Mercy) and old Metallica (Master and earlier albums/songs) as it'll cover fast alt picking and aslo downpicking a'la Hetfield. The woman asking him all of these questions has no idea who he is lmfao!
Iron Maiden. Start at Invaders and end at Rime of the Ancient Mariner. Every song.
Powerslave from start to finish was my bass endurance practice routine back in the day, haha. But while all of their albums are fun - I'd recommend Number of the Beast, Piece of Mind, and Powerslave. Just because.
The first song i learned COMPLETELY (all parts other than drums) was Nothing Else Matters by Metallica. Very simple to learn, including the solo which is still saucy even without being a shredfest. Of course the best part is when you find someone else that REALLY knows it and you can jam on it.
Orion was one of the first songs I learned with all of the leads. Its a nice walking tempo and the solos aren't too difficult
Most of my bread and butter when it came to learning guitar was Metallica and Offspring (another great band to learn; solos may be a bit quick, but there are not any real technical licks in them)