I loved "A First Course in Abstract Algebra" by Fraleigh. It was a while ago, so I don't quite remember whether it had solutions for the exercises or not.

[edit]: There's also Michael Artin's "Algebra" which is somewhat dense (certainly without solutions), but a very fascinating read due to its emphasis on symmetry groups. Particularly useful and enlightening in the context of modern particle physics.

Fraleigh contains solutions to the odd numbered sections (7th edition). It was the text I used (and enjoyed). I still have a copy of it, three years later.

When I was first trying to teach myself abstract algebra, Herstein's book seemed the most user-friendly. It doesn't go very far, but it's very clear and well-written. No solutions I'm afraid - but that's not common with any mathematics textbooks.