At the risk of being a little pedantic, I think Ruby is a great choice (Rails being a web framework). Sinatra is much more lightweight Ruby framework that I personally think is more appropriate when starting out. It offers far fewer abstractions (or, "magic") and is a radically simpler beast. To put some numbers on that assertion, the codebase itself is less than 1/100th the size of Rails.
If working with a different language, I recommend starting with some similar level of abstraction. Sinatra-esque frameworks typically offer enough functionality to make development fun while not obfuscating too much of the logic. Spark (Java) is Sinatra inspired. While I've never seriously developed in Python, web.py has been on my to-use list for quite some time.
I started trying to learn Rails at the same time that I was learning Ruby. That was a bad choice and I gave up after a couple months. When I started back at it recently, I dove straight into Ruby alone and left the frameworks out of it. After I felt comfortable enough in Ruby, I added Sinatra and love it.
Rails is powerful, but Sinatra is "just enough" for beginners like us.
If you think Rails is a poor first choice - what's your recommended language and why?