Random thoughts
My first experiences with programming were with Commodore Basic and assembler (sort of). The problem with learning programming that way is, that you often end up seeing programs as a list of instructions. Do this, do that, poke around until it works. Up-front algorithm design is nice but not required. Structured/procedural/imperative languages are less messy than BASIC or assembler, but they still allow for the same style. By contrast, if you try programming like that in a language like Scheme, you’ll end up with a big old mess pretty fast. In Haskell, you probably won’t even get started.
There is definitely something to be said for Logo as a beginner’s language. It’s not a popular choice nowadays, but one of the first things you learn is to split up programs into smaller, reusable parts. Turtle allows you to experiment and get immediate, visual feedback when you change something.
Note to self: Look for possible Logo(-esque) implementations for iPad/Android. I have a smart 3-year-old running around here, it would be interesting to see what she could do. :)