M-SPC is typically the chord Alt-Space, which activates the window menu
on many systems, both X and Windows, and is consumed by the window
manager before Emacs can get to it. At least that's the case on the
gnome 3.8 system I'm typing this on. And I would not want to disable
the binding for the window-menu as I like it's functionality and have
many years of muscle memory for it. So while M-SPC seems to me an
obvious variation on C-SPC, it should probably not be the primary way to
access this feature.
I _do_ think that this should be easily accessible. I have fond
memories of rectangular cut/copy/paste being a first class citizen in
the Brief text editor that I haven't used since probably '88. So I
would prefer as simple a chord (or sequence) as possible that still
identifies it as being just a variation on C-SPC.
So to the extent that there is a vote, I would go for either 'M-x SPC'
or 'C-SPC C-SPC', or 'C-M-SPC'.
Have you also considered, though, making rectangular regions work well
at the elisp level? For example, so many commands take (point mark)
from (interactive "r") and presume to think that it's a non-rectangular
region. Would it be useful to have a new interactive code that instead
supplies three arguments, (point mark shape) where shape is 'linear or
'rectangle.