I am trying to find a way to justify the creation of a single celled sentient (sorry intelligent) being. It's general structure is not specifically apparent although it should have the ability to either compel or "convince" other types of cells to do what it wishes. I am really unsure how to explain its existence. I had one idea, which was "these things just get created when humans time travel", but that just feels... A bit ridiculous to be honest. It kinda feels like a convenient cop out, and so I would rather look for other options.
I think you may find it more plausible if you leave the conventions of terrestrial biologies behind. The term 'single cell' connotes something of lesser complexity than a multi celled organism.
I suggest starting instead with the two largest challenges, Undifferentiated 'life' ( more on 'life) and 'intelligent' beings. I think that given the restrictions, something with properties of a liquid, or amorphous solid, as well as a flexible, but organized crystalline structure, (think silicon) would open possibilities for information storage in an electrochemical matrix, and maintain undifferentiated structure.
This may require some unusual and exotic chemistry, not just your standard C/N/H/O terrestrial ingredients.
Please also consider that 'life' and 'intelligence' might be trickier to define, when presented with something truly alien.
I hope this helps, good luck !
I've thought about a science fiction setting in which intelligent space-faring beings are the size of microorganisms.
The key is that intelligence is achieved through quantum-mechanical processes involving a small number of atoms, capable of fitting inside a single cell. The downside is that processing is not massively parallel like our brains! They exist on a much slower time scale. In my story, they experienced approximately 1 day for each human year.
In their ecosystem they have cells that are more like ours, too; they call it fast life and understand that blindingly fast reaction time and fecundity is another choice in being successful, as an alternative to the simple crystal structure and deliberate planning and intentional actions of being intelligent.
Or, you could simply go the route of James Blish and not explain it.
More generally, (I guess I was on a theme of very tiny intelligences) I looked at the computational complexity and capacity of the human brain and did some hard-science calculation that it could just fit in a mosquito. It would be hard pressed to be any smaller if made out of atoms, even when coming up with such clever ways to avoid wireing between them.
In order to work at all, without magic, you need a richer source of state. That's why I bring up quantum mechanics, as the Hilbert Space is unresonably large. Doing computation on this state and then reading out some kind of results without destroying it is a subject of deeper research, but at some point you start handwaving.
One way I could imagine a single cell organism gaining sentience would be through adopting of various strains of other organisms into its system. Kind of like we have mitochondria in our cells that make energy for the cell. Mitochondria have its own dna.
If at on some point (which could possibly be related to human time travel, by all means) a cell incorporated another simple organism (or more)into its system it could make it possible for the cell to both navigate and alter the behaviour of neighbouring cells. Or even more.