Well, I think I'll drop my wisdom in here, I think even the toned-down 600's are too much to start on. I started on a 250 Ninja, and it's got plenty of power for a beginner. It's also cheap to buy and cheap to insure. Definitely worth a look for your first bike.
As long as wheelies/stoppies/150mph blasts aren't on top of your to-do list, it'll keep you entertained for quite some time, while you develop the skills needed to control a motorcycle.
And definitely take the MSF. That will help no matter what bike you start off on.