Depends on your work flow, of course. I usually begin with coastlines, think about important harbors, bays, river inlets. Once I complete the coastlines, sometimes I rescale larger or smaller depending how the end map looks compared to what I wanted. I tend to create the oceans as an after thought, since in a vector program you can always create your ocean layer then place it below your continental layer.
It simply depends on which way you're more comfortable. To me, creating a rectangle first defines a limitation. I don't want to be limited when I create something. Its only in the final presentation that I frame the land with the proper ocean and possible map borders.
As opposed to CC3, I prefer to do my grid as the very last thing, rather than the first thing. Its this workflow in a vector drawing application that I prefer.