In a fairly graphics intsensive application the requirements state that it should default to full screen mode even though the application is running under Windows. I know many games do this but I find it annoying. The default IMO should be to open in a window rather than full screen mode. I am proposing the first time the user runs the application they should select the default behavior. Am I wrong?
I think the annoyance-factor depends a lot on what the application tries to do.
If it is some utility that I might start while working in 5 different applications and it forces its fullscreen-ness on my, then I'd get highly annoyed.
If it is a specialized application that helps me with the entire workflow of a given task (so that I never or rarely need any other apps open at the same time), then fullscreen might actually be a valid default.
Whatever you do, just make sure that toggling the startup behaviour is very discoverable. Because no matter which way you'll go, some of your users will disagree with your decision. And for them it should be very easy to change to their prefered way.