We already have a single byte that indicates presence of a memo field: the first byte of empty memos is 0xf6, and any initial byte lower than that indicates the presence of a text memo. It makes the ciphertext field of CompactOutput one byte longer, which would be the same for a single-bit field (as the unit-of-granularity for ciphertexts is bytes), but in exchange lets us only expose txids to the lightwalletd server for transactions we know have memos (which leaks a different, strictly smaller set of information). I argued early on that we should be downloading that extra byte per output in CompactBlocks, but was outvoted due to concerns about the increased bandwidth usage in the limit of high shielded usage.
We could start caching and serving it from lightwalletd (ProtoBuf arrays are variable-length), and this would be backwards-compatible for older light clients. It will make the logic slightly more complex for newer light clients than if we’d fetched it from the start, as we need to handle older lightwalletd servers that don’t provide it, but it’s doable. We could similarly add the entire memo field to outputs, or have a client flag to the server requesting one of the three combinations.