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.