By default, MSAA runs the pixel shader per-pixel, not per-sample (so if a triangle covers 3 samples, the PS still only runs once).
SSAA runs the pixel shader for every sample.

MSAA allows non-grid aligned sample positions, e.g. 2xMSAA over a 2x2 pixel area gives 8 sample locations, that might might look like:

|o |o |
| o| o|
+--+--+
|o |o |
| o| o|

SSAA samples are grid-aligned (when implemented by simply increasing render-target resolution).

Both MSAA and SSAA have the same memory usage, however MSAA might require less actual memory bandwidth due to HW compression schemes as mentioned above.

To add to what others have already said, with MSAA you have same guarantee that you have for the non-MSAA case: the sub-samples will be written to in draw order (and within a draw by triangle order). Generally you only get order-independent results when you're using depth writes and depth testing, since that will typically ensure that only the closest pixels/sub-samples end up being visible. So for instance if you're rendering transparents without depth writes, you'll get the same issues where you need to sort to ensure that you get correct results.

The only time this isn't the case is when using vendor-specific MSAA extensions (AMD's EQAA, and Nvidia's now-deprecated CSAA). These work by decoupling triangle coverage from depth and color storage, and the results will be somewhat order-dependent even with depth buffering. In practice though it's not a big deal, and these extensions aren't very popular to begin with (at least on PC).

Also, a quick shameless plug for an article that I wrote about MSAA: https://mynameismjp.wordpress.com/2012/10/24/msaa-overview/