@Luandro Pàtwy first to answer your question. SSB has always had the concept of OOO, meaning getting a message out of order. The message is valid in itself given that it is signed by the author. Interestingly if the messages themselves includes references to other messages that belong to the same subject (tangle), then you don't really need all the previous messages. This is what tangle sync is about. That is one form of partial replication. And if the messages are completely independent then getting them OOO style is completely fine.
Regarding message size I would probably look into bamboo and bamboo-rs that should work much better on lower powered devices. I believe @piet knows more about this.
I also remember that @cft had a fascinating talk on a related topic at the Basel meetup where one of his points if I remember correctly was that because the messages themselves include integrity, you don't really need it all the other layers of the stack to make sure that message are not corrupt, arrive in the right order etc. Can't find the slides now, but I'm sure he has something interesting to add here as well.