If there is a site that will let you play with strictly-validated HTML or something like that, I think that could be a good introduction to the idea of precise syntax without having to worry about algorithms or variables at first. But I agree that typically HTML is a bit too loose.
In fact now that I think about it, teaching syntax and semantics separately (eg with a stricter subset of HTML for the first and some sort of graphical programming thing like Scratch for the second) could be helpful for beginners.
People on this board have talked about programming as a gear in your brain that, to a first approximation, you have or you don't. I'm wondering if there's some well put-together resource you can direct someone with zero experience and just a web-browser to and say "if you're having fun an hour from now, you have the gear, good luck" -- maybe something on Khan academy?
(I learned to program a long time ago, and I started with BASIC program listings in my math textbook -- I don't actually know what the optimal onramps are now.)