Scheme worked wonderfully for me on this criteria. Even if it looks scary, as a newbie, I felt I knew what the interpreter was doing. This built my confidence much more than putting a lot of power in my hands that I didn't understand, like some other languages I tried first.
Scheme is awesome as long as you are mathematically fearless enough to learn from square one using books like How to Design Programs and The Structure and Interpretation of Computer Programs. They provide a great foundation if you feel right at home in math, and you're not too concerned with building something practical for your first project.
For people who aren't as confident in their math, I would recommend Python, as other have mentioned. It's thoroughly friendly to newcomers, there's tons of good documentation (the free tutorial written by Guido is incredible), the libraries are among the best available, and, like Scheme, it's easy to start by biting off a manageable chunk and then gradually learning more details as you go.