TL;DR: Solid focuses on storage and data formats, Sandstorm focuses on compute and protocols.
AIUI (disclaimer: haven't spent a huge amount of time studying it), Solid focuses on data and storage, not on compute. It proposes that each user's data should be stored in that user's own storage, under their control, in formats that are standardized so that they are compatible across multiple applications. The applications themselves, though, still execute as they do today, probably on servers owned by the developer. Applications interact with each other by virtue of supporting common formats. A big part of Solid is defining these standardized data formats.
Sandstorm is focused on compute: it says that applications running on your behalf should run on your own server, in isolated sandboxes. An application's storage format is a private implementation detail, and applications never directly access each other's storage. Instead, applications communicate via standardized protocols.
Abstractly, you can think of Sandstorm as object-oriented, in that it combines data and compute into an "object" that implements an "interface".
In my opinion (as the architect of Sandstorm), protocols are the correct place to find interoperability; data is the wrong place. The data format inherently defines the feature set which can be implemented on top of it, and thus forcing apps to use a standard data format tends to prevent them from implementing new features. It is much easier to create protocol compatibility because a complex app with a larger feature set can implement compatibility shims for other protocols using code.
Also, of course, Sandstorm's sandboxing model has huge security benefits. Solid doesn't seem to provide any security benefits since the apps still run remotely on the developers' servers where they could do anything they want with your data.
