When I took Abstract Algebra as part of my Math degree, we used Gallian, Herstein, and Judson. Gallian had a lot of examples and felt very much like the textbooks I used in high schools (colorful, lots of prose, etc.) It is incredibly easy to get into, but sometimes you've understood something and you don't need 25 more examples.
Herstein and Judson were both a less verbose (sometimes to the point of being unhelpful), but I'd still recommend them. I think I learned a lot from being exposed to different books. I could always look at another book if one book's explanations, examples, proofs, exercises were an issue. The Math Stackexchange was also invaluable because many of the proofs I saw there were very different from the ones I saw in class or in textbooks.