Hi!
I haven't managed to use my gmail account yet, and I guess it is due to the 2-step authentication process.
What do you mean by the 16 random characters? My Google authenticator app generates 6-digit passwords. But the Surface doesn't ask for this code anyway.
Yes, it is optional. If you are using it in association with an application (like an email client) you must go to a website and get an application specific password as the OP pointed out. Otherwise it will not work.
google 2 set authentication and application specific password
when you get to the account setting page on google - in browser, you have to generate a code - assign an id (anything but probably "my surface rt")
then use that to log in.